Codeforces Round 786 (Div. 3)

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
1674 Codeforces Round 786 (Div. 3) FINISHED False 7200 80321099 May 2, 2022, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 2536 ) G Remove Directed Edges PROGRAMMING dfs and similar dp graphs

B"You are given a directed acyclic graph, consisting of n vertices and m edges. The vertices are numbered from 1 to n . There are no multiple edges and self-loops. Let mathit{in}_v be the number of incoming edges (indegree) and mathit{out}_v be the number of outgoing edges (outdegree) of vertex v . You are asked to remove some edges from the graph. Let the new degrees be mathit{in'}_v and mathit{out'}_v . You are only allowed to remove the edges if the following conditions hold for every vertex v : Let's call a set of vertices S cute if for each pair of vertices v and u ( v neq u ) such that v in S and u in S , there exists a path either from v to u or from u to v over the non-removed edges. What is the maximum possible size of a cute set S after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to 0 ? The first line contains two integers n and m ( 1 <= n <= 2 cdot 10^5 ; 0 <= m <= 2 cdot 10^5 ) -- the number of vertices and the number of edges of the graph. Each of the next m lines contains two integers v and u ( 1 <= v, u <= n ; v neq u ) -- the description of an edge. The given edges form a valid directed acyclic graph. There are no multiple edges. Print a single integer -- the maximum possible size of a cute set S after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to 0 . In the first example, you can remove edges (1, 2) and (2, 3) . mathit{in} = [0, 1, 2] , mathit{out} = [2, 1, 0] . mathit{in'} = [0, 0, 1] , mathit{out'} = [1, 0, 0] . You can see that for all v the conditions hold. The maximum cute set S is formed by vertices 1 and 3 . They are still conn"...

Tutorials

102482

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
155739264 Hush G May 3, 2022, 8:36 a.m. OK GNU C++14 TESTS 27 78 5324800
155758418 Luminolic_Black G May 3, 2022, 12:01 p.m. OK GNU C++14 TESTS 27 93 8192000
155778780 walk_alone G May 3, 2022, 3:29 p.m. OK GNU C++14 TESTS 27 93 8294400
155729801 afengcode G May 3, 2022, 6:39 a.m. OK GNU C++14 TESTS 27 93 8294400
155740280 superstarch G May 3, 2022, 8:47 a.m. OK GNU C++14 TESTS 27 108 6656000
155732883 afengcode G May 3, 2022, 7:16 a.m. OK GNU C++14 TESTS 27 108 9113600
155763922 18913922290 G May 3, 2022, 1:02 p.m. OK GNU C++14 TESTS 27 109 8806400
155725449 rikka_cpp G May 3, 2022, 5:31 a.m. OK GNU C++14 TESTS 27 124 5324800
155805333 Unnamed-Cube G May 4, 2022, 2 a.m. OK GNU C++14 TESTS 27 124 6656000
155814256 haimo G May 4, 2022, 5:34 a.m. OK GNU C++14 TESTS 27 124 7065600
155772692 ytdnf G May 3, 2022, 2:09 p.m. OK GNU C++17 TESTS 27 108 6144000
155729392 Kanheyalal G May 3, 2022, 6:34 a.m. OK GNU C++17 TESTS 27 108 8499200
155773938 ytdnf G May 3, 2022, 2:25 p.m. OK GNU C++17 TESTS 27 109 6144000
155800813 birka0 G May 3, 2022, 11:09 p.m. OK GNU C++17 TESTS 27 109 6246400
155743772 Lemur95 G May 3, 2022, 9:23 a.m. OK GNU C++17 TESTS 27 109 6246400
155807541 muyuchenyin G May 4, 2022, 2:59 a.m. OK GNU C++17 TESTS 27 109 6860800
155784458 PineapplesOnPizza G May 3, 2022, 4:48 p.m. OK GNU C++17 TESTS 27 109 6860800
155740600 SaltedfishY G May 3, 2022, 8:50 a.m. OK GNU C++17 TESTS 27 109 7168000
155807417 zhangpangpang G May 4, 2022, 2:55 a.m. OK GNU C++17 TESTS 27 109 8192000
155797849 eashraf G May 3, 2022, 9:23 p.m. OK GNU C++17 TESTS 27 109 8192000
155747635 _Pioneer G May 3, 2022, 10:06 a.m. OK GNU C++17 (64) TESTS 27 77 6656000
155782630 Lucina G May 3, 2022, 4:21 p.m. OK GNU C++17 (64) TESTS 27 93 10444800
155736075 jinhan814 G May 3, 2022, 7:59 a.m. OK GNU C++17 (64) TESTS 27 108 9625600
155740731 Wang_Yuan G May 3, 2022, 8:52 a.m. OK GNU C++17 (64) TESTS 27 108 12288000
155761403 YoungChigga G May 3, 2022, 12:35 p.m. OK GNU C++17 (64) TESTS 27 109 10444800
155735110 Eter.nal G May 3, 2022, 7:46 a.m. OK GNU C++17 (64) TESTS 27 109 10444800
155729734 cjtodl G May 3, 2022, 6:38 a.m. OK GNU C++17 (64) TESTS 27 109 10444800
155786618 youtsuha G May 3, 2022, 5:22 p.m. OK GNU C++17 (64) TESTS 27 109 10854400
155784315 youtsuha2.0 G May 3, 2022, 4:46 p.m. OK GNU C++17 (64) TESTS 27 109 10854400
155737611 kh4ng G May 3, 2022, 8:16 a.m. OK GNU C++17 (64) TESTS 27 109 12492800
155736255 xjwwjx G May 3, 2022, 8:01 a.m. OK GNU C++20 (64) TESTS 27 62 6758400
155737548 yukito8069 G May 3, 2022, 8:16 a.m. OK GNU C++20 (64) TESTS 27 62 7475200
155736000 nlyh G May 3, 2022, 7:58 a.m. OK GNU C++20 (64) TESTS 27 77 6451200
155758251 LZVSDY G May 3, 2022, 11:59 a.m. OK GNU C++20 (64) TESTS 27 78 7987200
155754523 lintkey G May 3, 2022, 11:21 a.m. OK GNU C++20 (64) TESTS 27 93 8601600
155784182 mohantaashutosh G May 3, 2022, 4:44 p.m. OK GNU C++20 (64) TESTS 27 93 8806400
155756538 gaserashraf G May 3, 2022, 11:42 a.m. OK GNU C++20 (64) TESTS 27 93 9625600
155744347 AC_sahER G May 3, 2022, 9:29 a.m. OK GNU C++20 (64) TESTS 27 93 9830400
155813777 Swirl G May 4, 2022, 5:26 a.m. OK GNU C++20 (64) TESTS 27 93 10240000
155797070 abc3 G May 3, 2022, 9 p.m. OK GNU C++20 (64) TESTS 27 93 10240000
155744605 yunfeng G May 3, 2022, 9:32 a.m. OK Java 11 TESTS 27 561 33792000
155803273 NO__OB G May 4, 2022, 12:51 a.m. OK Java 11 TESTS 27 764 38400000
155763217 profchi G May 3, 2022, 12:55 p.m. OK Java 11 TESTS 27 1044 20275200
155778387 MagentaCobra G May 3, 2022, 3:24 p.m. OK Java 8 TESTS 27 374 40857600
155739173 ywjylx G May 3, 2022, 8:35 a.m. OK Java 8 TESTS 27 1154 35430400
155742993 CrashMaster G May 3, 2022, 9:16 a.m. OK MS C++ 2017 TESTS 27 514 30310400
155782692 shehebe G May 3, 2022, 4:22 p.m. OK PyPy 3 TESTS 27 1840 26316800
155782595 shehebe G May 3, 2022, 4:21 p.m. OK PyPy 3 TESTS 27 1872 33075200
155737486 june_waves G May 3, 2022, 8:15 a.m. OK PyPy 3-64 TESTS 27 1716 37376000
155782709 shehebe G May 3, 2022, 4:22 p.m. OK Python 3 TESTS 27 857 17715200
155812903 crazyboyani9117 G May 4, 2022, 5:10 a.m. OK Python 3 TESTS 27 1123 38297600
155804756 crazyboyani9117 G May 4, 2022, 1:43 a.m. OK Python 3 TESTS 27 1231 38502400

remove filters

Back to search problems