Kotlin Heroes: Episode 1

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
1170 Kotlin Heroes: Episode 1 FINISHED False 9000 178385087 May 28, 2019, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 75 ) G Graph Decomposition PROGRAMMING *special graphs

B'You are given an undirected graph consisting of n vertices and m edges. Recall that a cycle is a path that starts and ends in the same vertex. A cycle in a graph is called simple if it contains each vertex (except the starting and ending one) no more than once (the starting and the ending one is contained always twice). Note that loops are considered to be simple cycles. In one move you can choose any simple cycle in this graph and erase the edges corresponding to this cycle (corresponding vertices remain in the graph). It is allowed to erase the loop or two copies of the same edge (take a look at examples). Your problem is to apply some sequence of moves to obtain the graph without edges. It is not necessary to minimize the number of cycles. If it is impossible, print "NO". The first line of the input contains two integers n and m ( 1 <= n, m <= 2 cdot 10^5 ) -- the number of vertices and the number of edges in the graph. The next m lines contain edges of the graph. The i -th line contains the i -th edge x_i, y_i ( 1 <= x_i, y_i <= n ), where x_i and y_i are vertices connected by the i -th edge. The graph can contain loops or multiple edges. If it is impossible to decompose the given graph into simple cycles, print "NO" in the first line. Otherwise print "YES" in the first line. In the second line print k -- the number of simple cycles in the graph decomposition. In the next k lines print cycles themselves. The j -th line should contain the j -th cycle. First, print c_j -- the number of vertices in the j -th cycle. Then print the cycle as a sequence of vertices. All neighbouring (adjacent) vertices in the printed path should be connected by an edge that isn 't contained in other cycles. The picture corresponding to the first example: '...

Tutorials

Kotlin Heroes Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
55610779 ReaLNero1 G June 16, 2019, 5:35 a.m. OK Kotlin TESTS 88 467 31334400
55109226 TOXait G June 5, 2019, 5:16 a.m. OK Kotlin TESTS 88 468 31436800
54760213 eatmore G May 28, 2019, 3:40 p.m. OK Kotlin TESTS 88 483 31436800
54765664 knightL G May 28, 2019, 5:02 p.m. OK Kotlin TESTS 88 717 49766400
54844557 Ghaffargang G May 30, 2019, 1:14 p.m. OK Kotlin TESTS 88 748 59904000
54760498 Petr G May 28, 2019, 3:44 p.m. OK Kotlin TESTS 88 763 59904000
54778987 vadimmm G May 28, 2019, 7:55 p.m. OK Kotlin TESTS 88 764 43827200
59967265 Fortin G Sept. 3, 2019, 9:27 p.m. OK Kotlin TESTS 88 779 41267200
60017014 Fortin G Sept. 4, 2019, 12:06 p.m. OK Kotlin TESTS 88 779 41369600
54764052 DmitryGrigorev G May 28, 2019, 4:37 p.m. OK Kotlin TESTS 88 779 69017600

remove filters

Back to search problems