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 |
---|---|---|---|---|---|---|
1656 | CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) | FINISHED | False | 7200 | 89047463 | March 24, 2022, 2:35 p.m. |
Solved$ |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
---|---|---|---|---|---|---|
( 106 ) | I | Neighbour Ordering | PROGRAMMING | constructive algorithms graphs |
B"Given an undirected graph G , we say that a neighbour ordering is an ordered list of all the neighbours of a vertex for each of the vertices of G . Consider a given neighbour ordering of G and three vertices u , v and w , such that v is a neighbor of u and w . We write u <_{v} w if u comes after w in v 's neighbor list. A neighbour ordering is said to be good if, for each simple cycle v_1, v_2, ldots, v_c of the graph, one of the following is satisfied: Given a graph G , determine whether there exists a good neighbour ordering for it and construct one if it does. The input consists of multiple test cases. The first line contains a single integer t ( 1 <= q t <= q 10^4 ) -- the number of test cases. Description of the test cases follows. The first line of each test case contains two integers n and m ( 2 <= q n <= q 3 cdot 10^5 , 1 <= q m <= q 3 cdot 10^5 ), the number of vertices and the number of edges of the graph. The next m lines each contain two integers u, v ( 0 <= q u, v < n ), denoting that there is an edge connecting vertices u and v . It is guaranteed that the graph is connected and there are no loops or multiple edges between the same vertices. The sum of n and the sum of m for all test cases are at most 3 cdot 10^5 . For each test case, output one line with YES if there is a good neighbour ordering, otherwise output one line with NO. You can print each letter in any case (upper or lower). If the answer is YES, additionally output n lines describing a good neighbour ordering. In the i -th line, output the neighbours of vertex i in order. If there are multiple good neigbour orderings, print any. "... |
Tutorial |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
---|---|---|---|---|---|---|---|---|---|---|---|
150820717 | xbdhshshs | I | March 24, 2022, 6:53 p.m. | OK | GNU C++17 | TESTS | 27 | 2417 | 135987200 | ||
150839781 | ecnerwala | I | March 25, 2022, 1:37 a.m. | OK | GNU C++20 (64) | TESTS | 27 | 545 | 233164800 | ||
150825396 | ecnerwala | I | March 24, 2022, 7:47 p.m. | OK | GNU C++20 (64) | TESTS | 27 | 577 | 233164800 | ||
150827425 | maroonrk | I | March 24, 2022, 8:18 p.m. | OK | GNU C++20 (64) | TESTS | 27 | 1076 | 171622400 | ||
150821150 | Yashh123456 | I | March 24, 2022, 6:57 p.m. | OK | GNU C++20 (64) | TESTS | 27 | 2292 | 228352000 | ||
150819667 | higherorbit | I | March 24, 2022, 6:43 p.m. | OK | GNU C++20 (64) | TESTS | 27 | 2292 | 228352000 |
Back to search problems