Codeforces Round 438 by Sberbank and Barcelona Bootcamp (Div. 1 + Div. 2 combined)

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
868 Codeforces Round 438 by Sberbank and Barcelona Bootcamp (Div. 1 + Div. 2 combined) FINISHED False 10800 269218523 Oct. 5, 2017, 7:05 a.m.

Problems

Solved
Index
Name
Type
Tags
Community Tag
Rating
( 564 ) E Policeman and a Tree PROGRAMMING dp graphs trees 2600

You are given a tree (a connected non-oriented graph without cycles) with vertices numbered from 1 to n , and the length of the i -th edge is w i . In the vertex s there is a policeman, in the vertices x 1 , x 2 , ..., x m ( x j ≠ s ) m criminals are located. The policeman can walk along the edges with speed 1 , the criminals can move with arbitrary large speed. If a criminal at some moment is at the same point as the policeman, he instantly gets caught by the policeman. Determine the time needed for the policeman to catch all criminals, assuming everybody behaves optimally (i.e. the criminals maximize that time, the policeman minimizes that time). Everybody knows positions of everybody else at any moment of time. The first line contains single integer n ( 1 ≤ n ≤ 50 ) — the number of vertices in the tree. The next n - 1 lines contain three integers each: u i , v i , w i ( 1 ≤ u i , v i ≤ n , 1 ≤ w i ≤ 50 ) denoting edges and their lengths. It is guaranteed that the given graph is a tree. The next line contains single integer s ( 1 ≤ s ≤ n ) — the number of vertex where the policeman starts. The next line contains single integer m ( 1 ≤ m ≤ 50 ) — the number of criminals. The next line contains m integers x 1 , x 2 , ..., x m ( 1 ≤ x j ≤ n , x j ≠ s ) — the number of vertices where the criminals are located. x j are not necessarily distinct. If the policeman can't catch criminals, print single line " Terrorists win " (without quotes). Otherwise, print single integer — the time needed to catch all criminals. In the first example one of the optimal scenarios is the following. The criminal number 2 moves to vertex 3 , the criminal 4 — to vertex 4 . The policeman goes to vertex 4 and catches two criminals. After that the criminal number 1 moves to the vertex 2 . The policeman goes to vertex 3 and catches criminal 2 , then goes to the vertex 2 and catches the remaining criminal.

Tutorials

55046

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
31034758 guille E Oct. 5, 2017, 1:14 p.m. OK GNU C++ TESTS 53 31 102400 2600
31140972 langsike E Oct. 8, 2017, 10:41 a.m. OK GNU C++ TESTS 53 31 409600 2600
31021141 LoneFox E Oct. 5, 2017, 8:23 a.m. OK GNU C++ TESTS 53 93 0 2600
31590516 hwizard E Oct. 22, 2017, 3 a.m. OK GNU C++ TESTS 53 93 3686400 2600
31018209 fateice E Oct. 5, 2017, 7:55 a.m. OK GNU C++ TESTS 53 109 0 2600
31198027 wh2001_ZY E Oct. 10, 2017, 4:41 p.m. OK GNU C++ TESTS 53 109 102400 2600
31182614 vcvycy E Oct. 10, 2017, 6:45 a.m. OK GNU C++ TESTS 53 109 1536000 2600
33037754 KrK E Dec. 8, 2017, 11:05 p.m. OK GNU C++ TESTS 53 155 33689600 2600
31216463 xffyjq E Oct. 11, 2017, 12:46 p.m. OK GNU C++ TESTS 53 202 1331200 2600
32008590 sshockwave E Nov. 3, 2017, 1:33 p.m. OK GNU C++ TESTS 53 265 74956800 2600
31131548 sqrtdecompton E Oct. 8, 2017, 3:23 a.m. OK GNU C++11 TESTS 53 15 0 2600
31032140 sqrtdecompton E Oct. 5, 2017, 12:05 p.m. OK GNU C++11 TESTS 53 15 0 2600
31030667 Jakube E Oct. 5, 2017, 11:34 a.m. OK GNU C++11 TESTS 53 15 0 2600
31066349 niharika.3297 E Oct. 6, 2017, 1:01 p.m. OK GNU C++11 TESTS 53 30 0 2600
31047121 sqrtdecompton E Oct. 5, 2017, 9 p.m. OK GNU C++11 TESTS 53 30 0 2600
31146752 arasmus E Oct. 8, 2017, 2:28 p.m. OK GNU C++11 TESTS 53 30 102400 2600
57087519 lyslys E July 15, 2019, 9:28 a.m. OK GNU C++11 TESTS 53 31 0 2600
32045871 131441373 E Nov. 4, 2017, 7:53 a.m. OK GNU C++11 TESTS 53 31 0 2600
31131511 sqrtdecompton E Oct. 8, 2017, 3:20 a.m. OK GNU C++11 TESTS 53 31 0 2600
31119842 Stetsyk E Oct. 7, 2017, 3:11 p.m. OK GNU C++11 TESTS 53 31 0 2600
31065608 cxt E Oct. 6, 2017, 12:35 p.m. OK GNU C++14 TESTS 53 15 0 2600
31206291 mengrao E Oct. 11, 2017, 4:40 a.m. OK GNU C++14 TESTS 53 15 204800 2600
31022828 fram E Oct. 5, 2017, 8:41 a.m. OK GNU C++14 TESTS 53 15 204800 2600
31022026 AllCatsAreBeautiful E Oct. 5, 2017, 8:32 a.m. OK GNU C++14 TESTS 53 15 201830400 2600
31065567 cxt E Oct. 6, 2017, 12:34 p.m. OK GNU C++14 TESTS 53 31 0 2600
31045895 Rafiki53 E Oct. 5, 2017, 7:47 p.m. OK GNU C++14 TESTS 53 31 204800 2600
31025167 zigui E Oct. 5, 2017, 9:08 a.m. OK GNU C++14 TESTS 53 31 204800 2600
31019541 dotorya E Oct. 5, 2017, 8:06 a.m. OK GNU C++14 TESTS 53 31 204800 2600
31021742 JustasK E Oct. 5, 2017, 8:29 a.m. OK GNU C++14 TESTS 53 31 307200 2600
31026372 MrDindows E Oct. 5, 2017, 9:24 a.m. OK GNU C++14 TESTS 53 31 819200 2600
42247155 Benq E Aug. 29, 2018, 4 p.m. OK GNU C++17 TESTS 53 31 204800 2600
43629361 laurent.demonet E Oct. 1, 2018, 3:42 a.m. OK GNU C++17 TESTS 53 46 512000 2600
56553861 ppc_qjd E July 5, 2019, 11:22 a.m. OK GNU C++17 TESTS 53 78 204800 2600
60374141 ytrsk E Sept. 11, 2019, 5:16 a.m. OK GNU C++17 TESTS 53 93 27443200 2600
60374090 ytrsk E Sept. 11, 2019, 5:14 a.m. OK GNU C++17 TESTS 53 93 27443200 2600
60374034 ytrsk E Sept. 11, 2019, 5:11 a.m. OK GNU C++17 TESTS 53 109 27443200 2600
60373909 ytrsk E Sept. 11, 2019, 5:06 a.m. OK GNU C++17 TESTS 53 139 27545600 2600
68313620 AM. E Jan. 6, 2020, 12:20 p.m. OK GNU C++17 TESTS 53 187 54374400 2600
56605845 luogu_bot1 E July 6, 2019, 4:33 a.m. OK GNU C++17 TESTS 53 249 37580800 2600
56604704 charlieyan E July 6, 2019, 3:35 a.m. OK GNU C++17 TESTS 53 249 37580800 2600
31022409 Lewin E Oct. 5, 2017, 8:36 a.m. OK Java 8 TESTS 53 187 0 2600
32419422 SunshineJoy E Nov. 18, 2017, 3:39 a.m. OK Java 8 TESTS 53 530 0 2600
31018922 Petr E Oct. 5, 2017, 8:01 a.m. OK Java 8 TESTS 53 545 0 2600
38879678 vjudge4 E June 2, 2018, 8:34 a.m. OK MS C++ TESTS 53 124 5017600 2600

remove filters

Back to search problems