Codeforces Round 520 (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
1062 Codeforces Round 520 (Div. 2) FINISHED False 7200 195315923 Nov. 14, 2018, 3:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 686 ) F Upgrading Cities PROGRAMMING dfs and similar graphs 3000

B"There are n cities in the kingdom X , numbered from 1 through n . People travel between cities by some one-way roads. As a passenger, JATC finds it weird that from any city u , he can't start a trip in it and then return back to it using the roads of the kingdom. That is, the kingdom can be viewed as an acyclic graph. Being annoyed by the traveling system, JATC decides to meet the king and ask him to do something. In response, the king says that he will upgrade some cities to make it easier to travel. Because of the budget, the king will only upgrade those cities that are important or semi-important. A city u is called important if for every city v neq u , there is either a path from u to v or a path from v to u . A city u is called semi-important if it is not important and we can destroy exactly one city v neq u so that u becomes important. The king will start to act as soon as he finds out all those cities. Please help him to speed up the process. The first line of the input contains two integers n and m ( 2 <= n <= 300 ,000 , 1 <= m <= 300 ,000 ) -- the number of cities and the number of one-way roads. Next m lines describe the road system of the kingdom. Each of them contains two integers u_i and v_i ( 1 <= u_i, v_i <= n , u_i neq v_i ), denoting one-way road from u_i to v_i . It is guaranteed, that the kingdoms' roads make an acyclic graph, which doesn't contain multiple edges and self-loops. Print a single integer -- the number of cities that the king has to upgrade. In the first example: In the second example, the important cities are 1 and 4 . The semi-important cities are 2 and 3 . "...

Tutorials

Tutorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
55926522 shuitiacji F June 22, 2019, 9:34 a.m. OK GNU C++11 TESTS 64 46 13209600 3000
54586710 __23333 F May 25, 2019, 7:10 a.m. OK GNU C++11 TESTS 64 46 16896000 3000
54586667 __23333 F May 25, 2019, 7:10 a.m. OK GNU C++11 TESTS 64 46 16896000 3000
56830511 mmmod_lqs F July 11, 2019, 6:48 a.m. OK GNU C++11 TESTS 64 61 13209600 3000
54026465 M_sea F May 12, 2019, 12:55 p.m. OK GNU C++11 TESTS 64 61 13209600 3000
46142253 fwat F Nov. 24, 2018, 7:09 a.m. OK GNU C++11 TESTS 64 61 13209600 3000
64626959 Jackpei F Nov. 10, 2019, 8:51 a.m. OK GNU C++11 TESTS 64 62 9932800 3000
49179840 luogu_bot4 F Jan. 30, 2019, 12:30 a.m. OK GNU C++11 TESTS 64 62 9932800 3000
64724670 OuOu F Nov. 12, 2019, 5:56 a.m. OK GNU C++11 TESTS 64 62 12083200 3000
46281911 luogu_bot2 F Nov. 27, 2018, 1:47 p.m. OK GNU C++11 TESTS 64 62 12083200 3000
46234995 LittleFairyMY F Nov. 26, 2018, 1:22 a.m. OK GNU C++14 TESTS 64 139 18227200 3000
45797322 vjudge3 F Nov. 16, 2018, 11:34 a.m. OK GNU C++14 TESTS 64 155 18739200 3000
49057925 Acheing F Jan. 27, 2019, 2:07 p.m. OK GNU C++14 TESTS 64 156 10854400 3000
45798723 vjudge3 F Nov. 16, 2018, 12:13 p.m. OK GNU C++14 TESTS 64 171 18739200 3000
45856881 Zayin F Nov. 17, 2018, 2:41 a.m. OK GNU C++14 TESTS 64 187 16281600 3000
45758069 bibibibi F Nov. 15, 2018, 7:22 a.m. OK GNU C++14 TESTS 64 187 17920000 3000
53894077 Rabbittank F May 9, 2019, 4:01 a.m. OK GNU C++14 TESTS 64 202 16179200 3000
45802663 JSZX11556 F Nov. 16, 2018, 2:10 p.m. OK GNU C++14 TESTS 64 202 16179200 3000
46793872 LanaDelRey F Dec. 9, 2018, 9:07 a.m. OK GNU C++14 TESTS 64 218 16179200 3000
46136105 pipishrimp F Nov. 24, 2018, 5:55 a.m. OK GNU C++14 TESTS 64 233 25292800 3000
54976963 cjc F June 2, 2019, 11:18 a.m. OK GNU C++17 TESTS 64 171 18944000 3000
45751027 fcwww F Nov. 15, 2018, 1:05 a.m. OK GNU C++17 TESTS 64 186 10854400 3000
45802514 vjudge4 F Nov. 16, 2018, 2:05 p.m. OK GNU C++17 TESTS 64 187 16384000 3000
49205036 Mitsuhaw F Jan. 30, 2019, 1:39 p.m. OK GNU C++17 TESTS 64 217 16179200 3000
50519922 happy_ F Feb. 26, 2019, 8:50 a.m. OK GNU C++17 TESTS 64 218 17920000 3000
46035547 MMidori F Nov. 21, 2018, 4:08 p.m. OK GNU C++17 TESTS 64 218 55500800 3000
62442235 YouKn0wWho F Oct. 12, 2019, 8:05 p.m. OK GNU C++17 TESTS 64 233 18636800 3000
69436317 Mr.Robot_28 F Jan. 23, 2020, 7:08 p.m. OK GNU C++17 TESTS 64 249 20582400 3000
48867894 201530800126 F Jan. 24, 2019, 4:21 a.m. OK GNU C++17 TESTS 64 249 20889600 3000
48684899 Shayan.P F Jan. 21, 2019, 2:49 p.m. OK GNU C++17 TESTS 64 264 21196800 3000
47487942 donli F Dec. 25, 2018, 10:08 a.m. OK Java 8 TESTS 64 327 69017600 3000
46016281 BiIIy F Nov. 21, 2018, 3:52 a.m. OK Java 8 TESTS 64 374 45056000 3000
46016255 BiIIy F Nov. 21, 2018, 3:50 a.m. OK Java 8 TESTS 64 374 45056000 3000
47709301 sweiss F Dec. 30, 2018, 12:57 a.m. OK Java 8 TESTS 64 873 268390400 3000
46040469 annoreen F Nov. 21, 2018, 7:18 p.m. OK Java 8 TESTS 64 951 31846400 3000
45798651 zengxi F Nov. 16, 2018, 12:11 p.m. OK Java 8 TESTS 64 951 31846400 3000
45798717 vjudge2 F Nov. 16, 2018, 12:13 p.m. OK Java 8 TESTS 64 997 31846400 3000
47502104 Kirse F Dec. 25, 2018, 6:40 p.m. OK MS C++ TESTS 64 483 18124800 3000
67469881 vjudge1 F Dec. 23, 2019, 12:24 p.m. OK MS C++ TESTS 64 545 23040000 3000
51982893 kobae964 F March 29, 2019, 5:08 p.m. OK Rust TESTS 64 545 27545600 3000
51977370 kobae964 F March 29, 2019, 2:48 p.m. OK Rust TESTS 64 1341 31129600 3000

remove filters

Back to search problems