Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.
ContestId |
Name |
Phase |
Frozen |
Duration (Seconds) |
Relative Time |
Start Time |
---|---|---|---|---|---|---|
1770 | Good Bye 2022: 2023 is NEAR | FINISHED | False | 9000 | 64769063 | Dec. 30, 2022, 2:35 p.m. |
Solved$ |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
---|---|---|---|---|---|---|
( 1403 ) | E | Koxia and Tree | PROGRAMMING | combinatorics dp math probabilities trees |
B"Imi has an undirected tree with n vertices where edges are numbered from 1 to n-1 . The i -th edge connects vertices u_i and v_i . There are also k butterflies on the tree. Initially, the i -th butterfly is on vertex a_i . All values of a are pairwise distinct. Koxia plays a game as follows: Now, Koxia wants you to find the expected value of her score, modulo 998 ,244 ,353^ ddagger . ^ dagger The distance between two vertices on a tree is the number of edges on the (unique) simple path between them. ^ ddagger Formally, let M = 998 ,244 ,353 . It can be shown that the answer can be expressed as an irreducible fraction frac{p}{q} , where p and q are integers and q not equiv 0 pmod{M} . Output the integer equal to p cdot q^{-1} bmod M . In other words, output such an integer x that 0 <= x < M and x cdot q equiv p pmod{M} . The first line contains two integers n , k ( 2 <= q k <= q n <= q 3 cdot {10}^5 ) -- the size of the tree and the number of butterflies. The second line contains k integers a_1, a_2, ... , a_k ( 1 <= q a_i <= q n ) -- the initial position of butterflies. It's guaranteed that all positions are distinct. The i -th line in following n xe2 x88 x92 1 lines contains two integers u_i , v_i ( 1 <= q u_i, v_i <= q n , u_i neq v_i ) -- the vertices the i -th edge connects. It is guaranteed that the given edges form a tree. Output a single integer -- the expected value of Koxia's score, modulo 998 ,244 ,353 . In the first test case, the tree is shown below. Vertices containing butterflies are noted as bold. There are only 2 butterflies so the choice of butterflies is fixed. Let's consider the following 4 cases: Therefore, the expected value of Koxia's score is frac {1+1+2+1} {4} = frac {5} {4} , which is 748 ,683 ,266 after modu"... |
Good Bye 2022 -- Editorial |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
---|---|---|---|---|---|---|---|---|---|---|---|
187391786 | rainboy | E | Dec. 30, 2022, 9:48 p.m. | OK | GNU C11 | TESTS | 20 | 265 | 15564800 | ||
187395936 | xukai | E | Dec. 31, 2022, 12:22 a.m. | OK | GNU C++14 | TESTS | 20 | 280 | 18022400 | ||
187406105 | zltzlt | E | Dec. 31, 2022, 4:53 a.m. | OK | GNU C++14 | TESTS | 20 | 296 | 17203200 | ||
187399325 | no_dream | E | Dec. 31, 2022, 2:21 a.m. | OK | GNU C++14 | TESTS | 20 | 312 | 44134400 | ||
187423921 | triveni | E | Dec. 31, 2022, 8:29 a.m. | OK | GNU C++14 | TESTS | 20 | 342 | 16384000 | ||
187387296 | omeganot | E | Dec. 30, 2022, 8:16 p.m. | OK | GNU C++14 | TESTS | 20 | 342 | 19968000 | ||
187395473 | lvkaiyi0811 | E | Dec. 31, 2022, 12:03 a.m. | OK | GNU C++14 | TESTS | 20 | 342 | 39116800 | ||
187438831 | WyyOIer | E | Dec. 31, 2022, 11:21 a.m. | OK | GNU C++14 | TESTS | 20 | 343 | 17612800 | ||
187461617 | 72oced | E | Dec. 31, 2022, 3:47 p.m. | OK | GNU C++14 | TESTS | 20 | 358 | 16384000 | ||
187399711 | Tony2_CF | E | Dec. 31, 2022, 2:32 a.m. | OK | GNU C++14 | TESTS | 20 | 358 | 17612800 | ||
187403824 | WyyOIer | E | Dec. 31, 2022, 4:07 a.m. | OK | GNU C++14 | TESTS | 20 | 358 | 17612800 | ||
187493371 | TeasingMaster | E | Jan. 1, 2023, 4:54 a.m. | OK | GNU C++17 | TESTS | 20 | 202 | 27852800 | ||
187391455 | regain0001 | E | Dec. 30, 2022, 9:38 p.m. | OK | GNU C++17 | TESTS | 20 | 327 | 19968000 | ||
187405079 | FeTieTer | E | Dec. 31, 2022, 4:34 a.m. | OK | GNU C++17 | TESTS | 20 | 327 | 51814400 | ||
187384058 | Agreb | E | Dec. 30, 2022, 7:30 p.m. | OK | GNU C++17 | TESTS | 20 | 342 | 17612800 | ||
187402044 | maomao90 | E | Dec. 31, 2022, 3:27 a.m. | OK | GNU C++17 | TESTS | 20 | 342 | 18841600 | ||
187394773 | realcomplex | E | Dec. 30, 2022, 11:30 p.m. | OK | GNU C++17 | TESTS | 20 | 343 | 16384000 | ||
187431862 | catforces | E | Dec. 31, 2022, 10:01 a.m. | OK | GNU C++17 | TESTS | 20 | 358 | 19968000 | ||
187408955 | p_s_c_ | E | Dec. 31, 2022, 5:36 a.m. | OK | GNU C++17 | TESTS | 20 | 373 | 16384000 | ||
187436119 | code_struck | E | Dec. 31, 2022, 10:49 a.m. | OK | GNU C++17 | TESTS | 20 | 373 | 19558400 | ||
187436133 | 0x4c | E | Dec. 31, 2022, 10:49 a.m. | OK | GNU C++17 | TESTS | 20 | 374 | 16384000 | ||
187403167 | monstersqaq | E | Dec. 31, 2022, 3:52 a.m. | OK | GNU C++17 (64) | TESTS | 20 | 187 | 14540800 | ||
187413524 | Wuyanru | E | Dec. 31, 2022, 6:31 a.m. | OK | GNU C++17 (64) | TESTS | 20 | 265 | 14438400 | ||
187395354 | enslaved | E | Dec. 30, 2022, 11:59 p.m. | OK | GNU C++17 (64) | TESTS | 20 | 265 | 28057600 | ||
187486477 | Alex_Wei | E | Jan. 1, 2023, 12:22 a.m. | OK | GNU C++17 (64) | TESTS | 20 | 280 | 22016000 | ||
187396994 | maxwellzen | E | Dec. 31, 2022, 1:04 a.m. | OK | GNU C++17 (64) | TESTS | 20 | 280 | 22732800 | ||
187415421 | bashkort | E | Dec. 31, 2022, 6:50 a.m. | OK | GNU C++17 (64) | TESTS | 20 | 295 | 19968000 | ||
187447101 | antguz | E | Dec. 31, 2022, 12:56 p.m. | OK | GNU C++17 (64) | TESTS | 20 | 296 | 21196800 | ||
187403576 | Ethan_xu | E | Dec. 31, 2022, 4:02 a.m. | OK | GNU C++17 (64) | TESTS | 20 | 296 | 23552000 | ||
187402692 | xiaoyaowudi | E | Dec. 31, 2022, 3:42 a.m. | OK | GNU C++17 (64) | TESTS | 20 | 311 | 20275200 | ||
187394320 | Misono_Mika | E | Dec. 30, 2022, 11:13 p.m. | OK | GNU C++17 (64) | TESTS | 20 | 311 | 26726400 | ||
187383873 | islingr | E | Dec. 30, 2022, 7:28 p.m. | OK | GNU C++20 (64) | TESTS | 20 | 234 | 20889600 | ||
187469151 | ScarletS | E | Dec. 31, 2022, 5:20 p.m. | OK | GNU C++20 (64) | TESTS | 20 | 249 | 20070400 | ||
187457349 | 200815147 | E | Dec. 31, 2022, 2:56 p.m. | OK | GNU C++20 (64) | TESTS | 20 | 249 | 20070400 | ||
187478032 | tkacper | E | Dec. 31, 2022, 7:37 p.m. | OK | GNU C++20 (64) | TESTS | 20 | 249 | 20070400 | ||
187442695 | islingr | E | Dec. 31, 2022, 12:06 p.m. | OK | GNU C++20 (64) | TESTS | 20 | 249 | 20889600 | ||
187424605 | hijkl2e | E | Dec. 31, 2022, 8:37 a.m. | OK | GNU C++20 (64) | TESTS | 20 | 249 | 21196800 | ||
187485522 | anhkha2003 | E | Dec. 31, 2022, 11:29 p.m. | OK | GNU C++20 (64) | TESTS | 20 | 249 | 22425600 | ||
187391667 | puffins | E | Dec. 30, 2022, 9:44 p.m. | OK | GNU C++20 (64) | TESTS | 20 | 249 | 26316800 | ||
187402122 | comld | E | Dec. 31, 2022, 3:29 a.m. | OK | GNU C++20 (64) | TESTS | 20 | 249 | 48128000 | ||
187442332 | islingr | E | Dec. 31, 2022, 12:02 p.m. | OK | GNU C++20 (64) | TESTS | 20 | 264 | 20889600 | ||
187396687 | daftdove | E | Dec. 31, 2022, 12:54 a.m. | OK | Java 11 | TESTS | 20 | 1060 | 77004800 | ||
187395415 | profchi | E | Dec. 31, 2022, 12:01 a.m. | OK | Java 11 | TESTS | 20 | 1325 | 78848000 | ||
187401312 | Yu_212 | E | Dec. 31, 2022, 3:09 a.m. | OK | Java 17 | TESTS | 20 | 998 | 107827200 | ||
187427924 | YocyCraft | E | Dec. 31, 2022, 9:14 a.m. | OK | Java 8 | TESTS | 20 | 858 | 75468800 | ||
187489205 | golions | E | Jan. 1, 2023, 2:31 a.m. | OK | Java 8 | TESTS | 20 | 1123 | 102195200 | ||
187421899 | Hakiobo | E | Dec. 31, 2022, 8:04 a.m. | OK | Kotlin 1.6 | TESTS | 20 | 436 | 17510400 | ||
187403462 | USYDLDH | E | Dec. 31, 2022, 3:59 a.m. | OK | PyPy 3-64 | TESTS | 20 | 779 | 99123200 | ||
187401883 | Little_Sheep_Yawn | E | Dec. 31, 2022, 3:23 a.m. | OK | PyPy 3-64 | TESTS | 20 | 982 | 100761600 | ||
187433137 | jaaguptamme | E | Dec. 31, 2022, 10:15 a.m. | OK | PyPy 3-64 | TESTS | 20 | 2401 | 96870400 | ||
187432385 | jaaguptamme | E | Dec. 31, 2022, 10:07 a.m. | OK | PyPy 3-64 | TESTS | 20 | 2496 | 98611200 | ||
187432663 | jaaguptamme | E | Dec. 31, 2022, 10:10 a.m. | OK | PyPy 3-64 | TESTS | 20 | 2604 | 96972800 | ||
187411883 | Spheniscine | E | Dec. 31, 2022, 6:13 a.m. | OK | Rust 2021 | TESTS | 20 | 249 | 36352000 | ||
187412829 | Spheniscine | E | Dec. 31, 2022, 6:24 a.m. | OK | Rust 2021 | TESTS | 20 | 265 | 36352000 |
Back to search problems