Task: | Graph Ordering |
Sender: | koosaga |
Submission time: | 2024-01-01 01:29:08 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 7 |
#2 | ACCEPTED | 29 |
#3 | ACCEPTED | 18 |
#4 | ACCEPTED | 21 |
#5 | ACCEPTED | 25 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.24 s | 1, 4, 5 | details |
#2 | ACCEPTED | 0.24 s | 1, 5 | details |
#3 | ACCEPTED | 0.16 s | 1, 5 | details |
#4 | ACCEPTED | 0.21 s | 1, 5 | details |
#5 | ACCEPTED | 0.22 s | 1, 5 | details |
#6 | ACCEPTED | 0.03 s | 2, 3, 5 | details |
#7 | ACCEPTED | 0.03 s | 2, 3, 5 | details |
#8 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#9 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#10 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#11 | ACCEPTED | 0.03 s | 2, 3, 5 | details |
#12 | ACCEPTED | 0.03 s | 2, 3, 5 | details |
#13 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#14 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#15 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#16 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#17 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#18 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#19 | ACCEPTED | 0.03 s | 3, 4, 5 | details |
#20 | ACCEPTED | 0.03 s | 3, 4, 5 | details |
#21 | ACCEPTED | 0.03 s | 3, 4, 5 | details |
#22 | ACCEPTED | 0.03 s | 3, 4, 5 | details |
#23 | ACCEPTED | 0.03 s | 3, 5 | details |
#24 | ACCEPTED | 0.03 s | 3, 5 | details |
#25 | ACCEPTED | 0.03 s | 3, 5 | details |
#26 | ACCEPTED | 0.03 s | 3, 5 | details |
#27 | ACCEPTED | 0.03 s | 3, 5 | details |
#28 | ACCEPTED | 0.29 s | 5 | details |
#29 | ACCEPTED | 0.34 s | 5 | details |
#30 | ACCEPTED | 0.31 s | 4, 5 | details |
#31 | ACCEPTED | 0.31 s | 4, 5 | details |
#32 | ACCEPTED | 0.30 s | 4, 5 | details |
#33 | ACCEPTED | 0.31 s | 4, 5 | details |
#34 | ACCEPTED | 0.29 s | 5 | details |
#35 | ACCEPTED | 0.30 s | 5 | details |
#36 | ACCEPTED | 0.30 s | 5 | details |
#37 | ACCEPTED | 0.03 s | 1, 2, 3, 4, 5 | details |
#38 | ACCEPTED | 0.03 s | 2, 3, 5 | details |
#39 | ACCEPTED | 0.03 s | 2, 3, 5 | details |
#40 | ACCEPTED | 0.03 s | 2, 3, 5 | details |
#41 | ACCEPTED | 0.03 s | 1, 2, 3, 5 | details |
#42 | ACCEPTED | 0.03 s | 2, 3, 5 | details |
#43 | ACCEPTED | 0.03 s | 3, 4, 5 | details |
#44 | ACCEPTED | 0.03 s | 3, 4, 5 | details |
#45 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#46 | ACCEPTED | 0.03 s | 2, 3, 4, 5 | details |
#47 | ACCEPTED | 0.03 s | 2, 3, 5 | details |
#48 | ACCEPTED | 0.03 s | 3, 4, 5 | details |
#49 | ACCEPTED | 0.04 s | 4, 5 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:183:17: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized] 183 | if (!t) { | ^~ input/code.cpp:188:43: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized] 188 | auto p = storder(adj, s - 1, t - 1); | ^
Code
#include <bits/stdc++.h>#define sz(v) ((int)(v).size())#define all(v) (v).begin(), (v).end()#define cr(v, n) (v).clear(), (v).resize(n);using namespace std;using lint = long long;using pi = array<lint, 2>;// Given an undirected graph where G + {source, sink} is 2-vertex-connected// compute a permutation of vertices where// - the first vertex is a source// - the last vertex is a sink// - each non-source vertex has an adjacent vertex which appears earlier in the permutation// - each non-sink vertex has an adjacent vertex which appears later in the permutation// ref: https://codeforces.com/contest/1916/submission/239741602namespace std {template <class Fun> class y_combinator_result {Fun fun_;public:template <class T> explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}template <class... Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }};template <class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }} // namespace stdvector<int> storder(vector<vector<int>> adj, int source, int sink) {int N = int(adj.size());assert(N >= 2);assert(source != sink);adj[source].insert(adj[source].begin(), sink);adj[sink].insert(adj[sink].begin(), source);vector<int> depth(N, -1);vector<int> lowval(N);vector<bool> has_sink(N);vector<vector<int>> ch(N);y_combinator([&](auto self, int cur, int prv) -> void {depth[cur] = prv != -1 ? depth[prv] + 1 : 0;lowval[cur] = depth[cur];ch[cur].reserve(adj[cur].size());has_sink[cur] = (cur == sink);for (int nxt : adj[cur]) {if (nxt == prv)continue;if (depth[nxt] == -1) {ch[cur].push_back(nxt);self(nxt, cur);lowval[cur] = min(lowval[cur], lowval[nxt]);if (has_sink[nxt])has_sink[cur] = true;if (lowval[nxt] >= depth[cur] && !has_sink[nxt]) {// WARNING: This component will be directed arbitrarily.// In practice, we'll just make the first child an extra sink}} else if (depth[nxt] < depth[cur]) {lowval[cur] = min(lowval[cur], depth[nxt]);} else {// down edge}}})(source, -1);// true is after, false is beforevector<bool> edge_dir(N, false);vector<int> lst_nxt(N, -1);bool notbcc = false;auto lst = y_combinator([&](auto self, int cur) -> array<int, 2> {array<int, 2> res{cur, cur};for (int nxt : ch[cur]) {// If we're on the path to the sink, mark it as downwards.bool d;if (has_sink[nxt]) {d = true;} else if (lowval[nxt] >= depth[cur]) {notbcc = true;// continue;} else {d = !edge_dir[lowval[nxt]];}edge_dir[depth[cur]] = d;auto ch_res = self(nxt);// Join res and chif (!d)swap(res, ch_res);lst_nxt[exchange(res[1], ch_res[1])] = ch_res[0];}return res;})(source);if (notbcc)return {};vector<int> res(N);int cur = lst[0];for (int i = 0; i < N; i++) {res[i] = cur;cur = lst_nxt[cur];}return res;}const int MAXN = 400005;vector<int> gph[MAXN];vector<int> bcc[MAXN];vector<int> cmp[MAXN];int dfn[MAXN], low[MAXN], deg[MAXN], c, piv;int vis[MAXN];void color(int x, int p) {if (p) {bcc[p].push_back(x);cmp[x].push_back(p);}for (auto &i : gph[x]) {if (cmp[i].size())continue;if (low[i] >= dfn[x]) {bcc[++c].push_back(x);cmp[x].push_back(c);color(i, c);} elsecolor(i, p);}}void dfs(int x, int p) {vis[x] = 1;dfn[x] = low[x] = ++piv;for (auto &i : gph[x]) {if (i == p)continue;if (!dfn[i]) {dfs(i, x);low[x] = min(low[x], low[i]);} else {low[x] = min(low[x], dfn[i]);}}}int main() {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, m, s, t;cin >> n >> m;vector<vector<int>> adj(n);for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;gph[u].push_back(v);gph[v].push_back(u);u--;v--;adj[u].push_back(v);adj[v].push_back(u);}dfs(1, 0);color(1, 0);if (c == 1) {s = 1, t = 2;} else {for (int i = 1; i <= n; i++) {for (int j = 1; j < sz(cmp[i]); j++) {deg[cmp[i][0]]++;deg[cmp[i][j]]++;}}for (int i = 1; i <= c; i++) {if (deg[i] == 1) {t = s;for (auto &j : bcc[i]) {if (sz(cmp[j]) == 1)s = j;}}}if (!t) {cout << "IMPOSSIBLE\n";return 0;}}auto p = storder(adj, s - 1, t - 1);if (sz(p) == 0) {cout << "IMPOSSIBLE\n";return 0;}for (auto &v : p)cout << v + 1 << " ";}
Test details
Test 1
Group: 1, 4, 5
Verdict: ACCEPTED
input |
---|
100000 99999 8326 74462 11810 58064 21677 73087 62986 25005 ... |
correct output |
---|
1 44159 25721 84659 90058 9960... |
user output |
---|
100000 55408 4224 23528 55621 ... Truncated |
Test 2
Group: 1, 5
Verdict: ACCEPTED
input |
---|
100000 99999 28990 31200 86271 56882 61089 18658 52422 57504 ... |
correct output |
---|
68068 86325 91398 75677 51068 ... |
user output |
---|
68068 86325 91398 75677 51068 ... Truncated |
Test 3
Group: 1, 5
Verdict: ACCEPTED
input |
---|
100000 99999 29378 80094 12282 29378 96138 29378 61870 29378 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 4
Group: 1, 5
Verdict: ACCEPTED
input |
---|
100000 99999 97935 71091 9181 31715 73649 47675 45394 25464 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 5
Group: 1, 5
Verdict: ACCEPTED
input |
---|
100000 99999 2897 55594 11759 89041 56061 8717 69672 73046 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 6
Group: 2, 3, 5
Verdict: ACCEPTED
input |
---|
100 200 55 10 33 57 68 39 29 27 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 7
Group: 2, 3, 5
Verdict: ACCEPTED
input |
---|
100 175 71 86 100 88 83 92 25 73 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 8
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
100 200 26 58 49 25 66 20 20 85 ... |
correct output |
---|
1 2 86 60 34 92 23 4 44 89 76 ... |
user output |
---|
1 64 29 18 69 14 5 57 90 39 65... Truncated |
Test 9
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
100 195 19 28 63 48 1 57 1 20 ... |
correct output |
---|
12 97 18 74 36 10 78 50 61 95 ... |
user output |
---|
90 5 96 54 24 39 71 32 100 60 ... Truncated |
Test 10
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
100 193 48 66 15 67 32 14 36 78 ... |
correct output |
---|
1 56 13 32 14 49 75 93 18 6 54... |
user output |
---|
1 56 13 32 14 49 75 93 18 6 54... Truncated |
Test 11
Group: 2, 3, 5
Verdict: ACCEPTED
input |
---|
100 195 47 68 57 61 45 17 80 61 ... |
correct output |
---|
57 20 83 41 25 33 60 91 59 7 7... |
user output |
---|
19 23 2 10 3 64 63 98 86 21 34... Truncated |
Test 12
Group: 2, 3, 5
Verdict: ACCEPTED
input |
---|
100 185 43 78 76 99 78 39 83 61 ... |
correct output |
---|
78 43 32 88 26 28 64 81 7 72 2... |
user output |
---|
46 78 43 26 28 32 88 64 81 7 7... Truncated |
Test 13
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
99 132 96 16 18 89 98 50 66 26 ... |
correct output |
---|
1 12 45 71 97 22 35 9 60 27 20... |
user output |
---|
54 47 5 99 56 8 81 62 51 88 49... Truncated |
Test 14
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
98 144 25 6 30 34 58 25 31 41 ... |
correct output |
---|
32 7 92 1 63 86 87 14 90 17 81... |
user output |
---|
98 67 43 72 22 51 89 71 94 84 ... Truncated |
Test 15
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
96 145 19 70 72 92 27 72 17 85 ... |
correct output |
---|
1 50 30 4 10 48 42 5 70 19 29 ... |
user output |
---|
16 62 95 81 96 80 79 74 57 90 ... Truncated |
Test 16
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
96 158 79 74 41 70 8 5 73 90 ... |
correct output |
---|
7 59 44 27 1 30 49 28 80 52 15... |
user output |
---|
55 37 96 53 32 76 86 60 93 51 ... Truncated |
Test 17
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
96 142 95 35 67 89 91 70 48 21 ... |
correct output |
---|
13 20 81 33 1 51 19 69 16 85 6... |
user output |
---|
96 61 83 93 54 28 65 41 46 75 ... Truncated |
Test 18
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
72 111 70 17 25 3 58 24 52 9 ... |
correct output |
---|
21 59 48 8 1 2 31 10 11 41 4 5... |
user output |
---|
46 38 29 6 72 55 25 28 3 12 66... Truncated |
Test 19
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
988 1563 402 701 830 801 50 578 8 144 ... |
correct output |
---|
1 136 368 683 447 304 131 53 8... |
user output |
---|
535 201 672 99 132 988 154 586... Truncated |
Test 20
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
994 1555 171 541 66 915 330 350 494 251 ... |
correct output |
---|
1 164 205 151 951 797 4 654 14... |
user output |
---|
373 327 994 678 408 519 156 19... Truncated |
Test 21
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
1000 2000 711 947 775 441 691 471 844 28 ... |
correct output |
---|
1 676 731 662 248 31 165 558 8... |
user output |
---|
1 788 207 613 5 561 774 465 28... Truncated |
Test 22
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
1000 2000 811 889 873 984 83 52 144 511 ... |
correct output |
---|
60 909 522 568 40 77 181 441 8... |
user output |
---|
1 244 54 153 928 668 147 418 3... Truncated |
Test 23
Group: 3, 5
Verdict: ACCEPTED
input |
---|
1000 1869 625 715 448 714 110 927 432 1000 ... |
correct output |
---|
224 326 221 30 76 475 666 694 ... |
user output |
---|
224 326 221 30 982 475 666 694... Truncated |
Test 24
Group: 3, 5
Verdict: ACCEPTED
input |
---|
1000 1783 709 1 182 768 355 40 786 260 ... |
correct output |
---|
230 6 135 678 346 19 470 960 3... |
user output |
---|
19 346 678 135 6 230 470 318 9... Truncated |
Test 25
Group: 3, 5
Verdict: ACCEPTED
input |
---|
1000 2000 92 876 273 598 287 535 526 972 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 26
Group: 3, 5
Verdict: ACCEPTED
input |
---|
1000 1910 789 821 553 740 889 527 488 730 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 27
Group: 3, 5
Verdict: ACCEPTED
input |
---|
1000 1608 910 416 503 898 928 14 412 903 ... |
correct output |
---|
140 404 739 563 63 794 623 948... |
user output |
---|
577 799 656 797 289 598 294 66... Truncated |
Test 28
Group: 5
Verdict: ACCEPTED
input |
---|
100000 198666 5659 89691 91040 53375 96642 56177 28768 57001 ... |
correct output |
---|
45598 74078 1039 83702 16344 8... |
user output |
---|
47465 70485 75697 65582 90639 ... Truncated |
Test 29
Group: 5
Verdict: ACCEPTED
input |
---|
100000 197194 41636 91770 63018 23827 39207 93713 67765 47715 ... |
correct output |
---|
79054 61855 53279 55546 60860 ... |
user output |
---|
17707 98305 73225 38546 97115 ... Truncated |
Test 30
Group: 4, 5
Verdict: ACCEPTED
input |
---|
100000 199985 13674 42886 51349 6858 78502 18751 13628 65936 ... |
correct output |
---|
17857 81664 4369 61462 79754 8... |
user output |
---|
1 47064 44643 17857 73639 8166... Truncated |
Test 31
Group: 4, 5
Verdict: ACCEPTED
input |
---|
100000 200000 27666 33166 7161 81452 73134 30281 5106 29308 ... |
correct output |
---|
76869 5635 23236 12666 61633 8... |
user output |
---|
1 73905 50785 14730 66904 9004... Truncated |
Test 32
Group: 4, 5
Verdict: ACCEPTED
input |
---|
100000 200000 62814 54729 98407 26888 91808 70132 58916 49730 ... |
correct output |
---|
19788 11202 3496 24237 68564 5... |
user output |
---|
1 75042 96858 87874 11202 3496... Truncated |
Test 33
Group: 4, 5
Verdict: ACCEPTED
input |
---|
100000 200000 2299 91653 21125 75544 54029 94067 86513 45051 ... |
correct output |
---|
1 20339 9304 40427 67694 95656... |
user output |
---|
1 67687 2467 66521 2098 1694 5... Truncated |
Test 34
Group: 5
Verdict: ACCEPTED
input |
---|
100000 200000 34688 93668 78127 18902 55150 33116 273 88797 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 35
Group: 5
Verdict: ACCEPTED
input |
---|
100000 200000 21026 14630 5605 59639 25604 78683 55713 70513 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 36
Group: 5
Verdict: ACCEPTED
input |
---|
100000 200000 63190 73606 52072 54105 22092 31495 9189 37924 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 37
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
2 1 2 1 |
correct output |
---|
1 2 |
user output |
---|
1 2 |
Test 38
Group: 2, 3, 5
Verdict: ACCEPTED
input |
---|
7 9 1 2 1 3 2 3 1 4 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 39
Group: 2, 3, 5
Verdict: ACCEPTED
input |
---|
9 12 1 2 2 3 3 1 4 5 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 40
Group: 2, 3, 5
Verdict: ACCEPTED
input |
---|
5 5 4 2 4 3 2 1 3 1 ... |
correct output |
---|
4 2 3 1 5 |
user output |
---|
5 1 2 4 3 |
Test 41
Group: 1, 2, 3, 5
Verdict: ACCEPTED
input |
---|
4 3 1 2 3 2 4 2 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 42
Group: 2, 3, 5
Verdict: ACCEPTED
input |
---|
17 30 4 1 3 14 6 16 13 6 ... |
correct output |
---|
7 8 11 15 1 2 9 3 14 13 5 10 1... |
user output |
---|
15 11 8 7 1 4 2 9 3 14 5 10 17... |
Test 43
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
992 1712 377 709 847 640 261 902 761 693 ... |
correct output |
---|
870 1 925 928 950 257 766 520 ... |
user output |
---|
992 189 812 397 391 411 372 88... Truncated |
Test 44
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
990 1672 305 445 800 155 365 779 824 247 ... |
correct output |
---|
108 461 160 696 895 655 376 21... |
user output |
---|
990 783 413 194 258 454 851 45... Truncated |
Test 45
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
99 169 35 32 97 43 22 62 33 7 ... |
correct output |
---|
19 70 62 22 54 78 25 14 3 81 1... |
user output |
---|
88 10 12 24 58 85 95 2 89 93 8... Truncated |
Test 46
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
99 164 62 73 19 35 55 92 79 91 ... |
correct output |
---|
21 25 64 90 17 15 89 95 70 33 ... |
user output |
---|
99 80 47 52 31 73 62 51 58 39 ... Truncated |
Test 47
Group: 2, 3, 5
Verdict: ACCEPTED
input |
---|
53 68 7 46 51 14 3 18 8 40 ... |
correct output |
---|
32 30 38 33 27 12 8 20 2 34 45... |
user output |
---|
11 6 35 10 42 21 9 24 49 5 37 ... Truncated |
Test 48
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
996 1902 661 201 19 613 895 438 180 32 ... |
correct output |
---|
220 795 198 239 40 164 773 834... |
user output |
---|
252 996 693 103 240 288 77 330... Truncated |
Test 49
Group: 4, 5
Verdict: ACCEPTED
input |
---|
6110 11528 3366 4718 3226 2188 5022 1186 3205 5349 ... |
correct output |
---|
1 2527 2211 554 4201 4522 1494... |
user output |
---|
1322 6110 3818 5199 4064 3418 ... Truncated |