Codeforces Round 868 (Div. 2)

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
1823 Codeforces Round 868 (Div. 2) FINISHED False 7200 54573863 April 27, 2023, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 919 ) F Random Walk PROGRAMMING dp graphs math probabilities trees

B"You are given a tree consisting of n vertices and n - 1 edges, and each vertex v has a counter c(v) assigned to it. Initially, there is a chip placed at vertex s and all counters, except c(s) , are set to 0 ; c(s) is set to 1 . Your goal is to place the chip at vertex t . You can achieve it by a series of moves. Suppose right now the chip is placed at the vertex v . In one move, you do the following: You'll repeat the move above until you reach the vertex t . For each vertex v calculate the expected value of c(v) modulo 998 ,244 ,353 . The first line contains three integers n , s and t ( 2 <= n <= 2 cdot 10^5 ; 1 <= s, t <= n ; s neq t ) -- number of vertices in the tree and the starting and finishing vertices. Next n - 1 lines contain edges of the tree: one edge per line. The i -th line contains two integers u_i and v_i ( 1 <= u_i, v_i <= n ; u_i neq v_i ), denoting the edge between the nodes u_i and v_i . It's guaranteed that the given edges form a tree. Print n numbers: expected values of c(v) modulo 998 ,244 ,353 for each v from 1 to n . 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 tree from the first example is shown below: "...

Tutorials

115465

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
203730824 LBRhhhh F April 27, 2023, 7 p.m. OK GNU C++14 TESTS 21 202 16998400
203733083 sinus_070 F April 27, 2023, 7:29 p.m. OK GNU C++14 TESTS 21 233 16998400
203701524 45645B F April 27, 2023, 3:41 p.m. OK GNU C++14 TESTS 20 234 16793600
203702886 rfpermen F April 27, 2023, 3:46 p.m. OK GNU C++14 TESTS 20 249 27852800
203766137 Krystallos F April 28, 2023, 5:38 a.m. OK GNU C++14 TESTS 21 265 18636800
203705320 wzh_2007 F April 27, 2023, 3:54 p.m. OK GNU C++14 TESTS 20 265 28569600
203713776 chenguoyi F April 27, 2023, 4:27 p.m. OK GNU C++14 TESTS 20 280 15974400
203738783 FatihSolak F April 27, 2023, 8:54 p.m. OK GNU C++14 TESTS 21 358 25190400
203728001 nush24 F April 27, 2023, 6:29 p.m. OK GNU C++14 TESTS 21 483 26624000
203715624 Steven__Chen F April 27, 2023, 4:33 p.m. OK GNU C++14 TESTS 20 499 26624000

remove filters

Back to search problems