Good Bye 2022: 2023 is NEAR

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.

Problems

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"...

Tutorials

Good Bye 2022 -- Editorial

Submissions

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

remove filters

Back to search problems