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. |
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. |
| 55046 |
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 |
Back to search problems