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.
Problems
B"Alice and Bob are playing a game. They have a tree consisting of n vertices. Initially, Bob has k chips, the i -th chip is located in the vertex a_i (all these vertices are unique). Before the game starts, Alice will place a chip into one of the vertices of the tree. The game consists of turns. Each turn, the following events happen (sequentially, exactly in the following order): The game ends when Alice's chip shares the same vertex with one (or multiple) of Bob's chips. Note that Bob's chips may share the same vertex, even though they are in different vertices at the beginning of the game. Alice wants to maximize the number of turns, Bob wants to minimize it. If the game ends in the middle of some turn (Alice moves her chip to a vertex that contains one or multiple Bob's chips), this turn is counted. For each vertex, calculate the number of turns the game will last if Alice places her chip in that vertex. The first line contains one integer n ( 2 <= n <= 2 cdot 10^5 ) -- the number of vertices in the tree. Then n - 1 lines follow, each line contains two integers u_i , v_i ( 1 <= u_i, v_i <= n ; u_i ne v_i ) that denote the endpoints of an edge. These edges form a tree. The next line contains one integer k ( 1 <= k <= n - 1 ) -- the number of Bob's chips. The last line contains k integers a_1 , a_2 , ..., a_k ( 1 <= a_i <= n ; a_i ne a_j if i ne j ) -- the vertices where the Bob's chips are initially placed. Print n integers. The i -th of them should be equal to the number of turns the game will last if Alice initially places her chip in the vertex i . If one of Bob's chips is already placed in vertex i , then the answer for vertex i is 0 . "... |
Tutorials
Submissions
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
98981551 |
sh1194 |
G |
Nov. 19, 2020, 7 p.m. |
OK |
GNU C++14 |
TESTS |
138 |
608 |
16076800 |
|
|
98981631 |
sh1194 |
G |
Nov. 19, 2020, 7:02 p.m. |
OK |
GNU C++14 |
TESTS |
138 |
670 |
16076800 |
|
|
98981784 |
sh1194 |
G |
Nov. 19, 2020, 7:05 p.m. |
OK |
GNU C++14 |
TESTS |
138 |
701 |
16076800 |
|
|
98949766 |
easeen56 |
G |
Nov. 19, 2020, 4:58 p.m. |
OK |
GNU C++14 |
TESTS |
138 |
732 |
16076800 |
|
|
98945555 |
MarcoMeijer |
G |
Nov. 19, 2020, 4:33 p.m. |
OK |
GNU C++17 |
TESTS |
138 |
374 |
22937600 |
|
|
98940943 |
jdurie |
G |
Nov. 19, 2020, 4:17 p.m. |
OK |
GNU C++17 |
TESTS |
138 |
374 |
45772800 |
|
|
98987572 |
kefaa2 |
G |
Nov. 19, 2020, 9:42 p.m. |
OK |
GNU C++17 |
TESTS |
138 |
826 |
22732800 |
|
|
98978490 |
rainboy |
G |
Nov. 19, 2020, 6:06 p.m. |
OK |
GNU C++17 |
TESTS |
138 |
842 |
21913600 |
|
|
98981487 |
jairadheyshyam |
G |
Nov. 19, 2020, 6:59 p.m. |
OK |
GNU C++17 |
TESTS |
138 |
888 |
14336000 |
|
|
98978591 |
ma_da_fu_ka |
G |
Nov. 19, 2020, 6:07 p.m. |
OK |
GNU C++17 |
TESTS |
138 |
1013 |
16076800 |
|
|
98943421 |
peti1234 |
G |
Nov. 19, 2020, 4:26 p.m. |
OK |
GNU C++17 |
TESTS |
138 |
1013 |
16076800 |
|
|
98983736 |
kefaa2 |
G |
Nov. 19, 2020, 7:48 p.m. |
OK |
GNU C++17 |
TESTS |
138 |
1107 |
25702400 |
|
|
99002175 |
PurpleCrayon |
G |
Nov. 20, 2020, 5:58 a.m. |
OK |
GNU C++17 |
TESTS |
138 |
1637 |
94720000 |
|
|
98988754 |
PauloMiranda98 |
G |
Nov. 19, 2020, 10:33 p.m. |
OK |
GNU C++17 (64) |
TESTS |
138 |
264 |
31232000 |
|
|
98984598 |
wrinx |
G |
Nov. 19, 2020, 8:11 p.m. |
OK |
GNU C++17 (64) |
TESTS |
138 |
296 |
36864000 |
|
|
98977000 |
Asriel_Dreemurr |
G |
Nov. 19, 2020, 5:42 p.m. |
OK |
GNU C++17 (64) |
TESTS |
138 |
1294 |
121036800 |
|
|
98944458 |
2016wudi |
G |
Nov. 19, 2020, 4:29 p.m. |
OK |
GNU C++17 (64) |
TESTS |
138 |
1465 |
32256000 |
|
|
98946521 |
emengdeath |
G |
Nov. 19, 2020, 4:36 p.m. |
OK |
GNU C++17 (64) |
TESTS |
138 |
1934 |
43417600 |
|
|
remove filters
Back to search problems