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