Codeforces Round 856 (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
1794 Codeforces Round 856 (Div. 2) FINISHED False 7200 59228663 March 4, 2023, 5:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 1135 ) E Labeling the Tree with Distances PROGRAMMING data structures dp hashing implementation trees

B'You are given an unweighted tree of n vertices numbered from 1 to n and a list of n-1 integers a_1, a_2, ldots, a_{n-1} . A tree is a connected undirected graph without cycles. You will use each element of the list to label one vertex. No vertex should be labeled twice. You can label the only remaining unlabeled vertex with any integer. A vertex x is called good if it is possible to do this labeling so that for each vertex i , its label is the distance between x and i . The distance between two vertices s and t on a tree is the minimum number of edges on a path that starts at vertex s and ends at vertex t . Find all good vertices. The first line contains one integer n ( 2 <= n <= 2 cdot 10^5 ) -- the number of vertices in the tree. The second line contains n - 1 integers a_1,a_2, ldots,a_{n-1} ( 0 <= a_i < n ) -- the given list. Then, n xe2 x88 x921 lines follow. Each of them contains two integers u and v ( 1 <= u,v <= n ) denoting an edge between vertices u and v . It is guaranteed that the edges form a tree. In the first line print the number of good vertices. In the second line, print the indices of all good vertices in ascending order. This is the tree for the first example: And these are two possible labelings with the elements on the list so that 2 is a good vertex (left) and 4 is a good vertex (right). The square below each vertex represents its label. The black squares contain the numbers which were on the given list and the only white square contains the only number which was not on the given list. In the second example, the only good vertex is vertex 3 . In the third example, there are no good vertices. '...

Tutorials

Codeforces Round 856 (Div. 2) Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
196043313 mban259 E March 4, 2023, 6:55 p.m. OK C# 10 TESTS 120 623 86425600
196060522 I_am_not_good_at_CP E March 4, 2023, 8:23 p.m. OK GNU C++14 TESTS 120 420 20787200
196081538 Monkemonk E March 5, 2023, 3:22 a.m. OK GNU C++14 TESTS 148 499 36249600
196089883 Shui_Dream E March 5, 2023, 5:39 a.m. OK GNU C++14 TESTS 175 530 40243200
196044163 Bliss_of_comprehension E March 4, 2023, 6:58 p.m. OK GNU C++14 TESTS 120 561 43417600
196089803 ccqyx123 E March 5, 2023, 5:37 a.m. OK GNU C++14 TESTS 175 561 57958400
196089930 ccqyx123 E March 5, 2023, 5:39 a.m. OK GNU C++14 TESTS 175 638 57958400
196059943 A.n.o.n.y.m.o.u.s E March 4, 2023, 8:20 p.m. OK GNU C++14 TESTS 120 639 55500800
196061733 Seast E March 4, 2023, 8:33 p.m. OK GNU C++14 TESTS 120 811 44134400
196091314 wangzirui123 E March 5, 2023, 5:56 a.m. OK GNU C++14 TESTS 177 1044 195481600
196049802 Kaitokid E March 4, 2023, 7:15 p.m. OK GNU C++14 TESTS 120 1325 67993600

remove filters

Back to search problems