# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
747589 | 2023-05-24T11:14:24 Z | math_rabbit_1028 | Thousands Islands (IOI22_islands) | C++17 | 294 ms | 26844 KB |
#include "islands.h" #include <bits/stdc++.h> using namespace std; bool ans = false; vector<int> res; int n, m; vector< pair<int, int> > adj[101010], rev[101010]; int out[101010], in[101010], remain[202020]; set< pair<int, int> > outset; int ch[202020], ch2[202020]; vector<int> path1, path2, cycle, path3, cycle2; int junc; void DFS(int v) { int cnt = 0; for (int i = 0; i < adj[v].size(); i++) { if (remain[adj[v][i].second] == 0) continue; if (ch[adj[v][i].first] == 0) { cnt++; } } if (cnt >= 2) { ans = true; junc = v; return; } for (int i = 0; i < adj[v].size(); i++) { if (remain[adj[v][i].second] == 0) continue; if (ch[adj[v][i].first] == 0) { ch[adj[v][i].first] = 1; path1.push_back(adj[v][i].second); DFS(adj[v][i].first); } } } int st = -1; void path(int v) { for (int i = 0; i < adj[v].size(); i++) { if (remain[adj[v][i].second] == 0) continue; if (ch[adj[v][i].first] == 0) { ch[adj[v][i].first] = 1; ch2[adj[v][i].first] = 1; path2.push_back(adj[v][i].second); path(adj[v][i].first); if (st >= 0) return; } else if (ch2[adj[v][i].first] == 1) { path2.push_back(adj[v][i].second); st = adj[v][i].first; return; } } path2.pop_back(); } bool isconnect = false; int iscycle[101010]; void check(int v) { if (iscycle[v] == 1) { st = v; isconnect = true; return; } for (int i = 0; i < adj[v].size(); i++) { if (remain[adj[v][i].second] == 0) continue; if (ch[adj[v][i].first] == 0) { ch[adj[v][i].first] = 1; path3.push_back(adj[v][i].second); check(adj[v][i].first); if (isconnect) return; } } path3.pop_back(); } int other_st = -1; void other_path(int v) { for (int i = 0; i < adj[v].size(); i++) { if (remain[adj[v][i].second] == 0) continue; if (ch[adj[v][i].first] == 0) { ch[adj[v][i].first] = 1; ch2[adj[v][i].first] = 1; path3.push_back(adj[v][i].second); other_path(adj[v][i].first); if (other_st >= 0) return; } else if (ch2[adj[v][i].first] == 1) { path3.push_back(adj[v][i].second); other_st = adj[v][i].first; return; } } path3.pop_back(); } std::variant<bool, std::vector<int>> find_journey( int N, int M, std::vector<int> U, std::vector<int> V) { n = N; m = M; for (int i = 0; i < m; i++) { adj[U[i]].push_back({V[i], i}); rev[V[i]].push_back({U[i], i}); out[U[i]]++; in[V[i]]++; remain[i] = 1; } for (int i = 0; i < n; i++) outset.insert({out[i], i}); while (!outset.empty() && outset.begin()->first == 0) { int v = outset.begin()->second; outset.erase(outset.begin()); for (int i = 0; i < rev[v].size(); i++) { if (remain[rev[v][i].second] == 0) continue; remain[rev[v][i].second] = 0; outset.erase(outset.find(make_pair(out[rev[v][i].first], rev[v][i].first))); out[rev[v][i].first]--; outset.insert(make_pair(out[rev[v][i].first], rev[v][i].first)); } } if (out[0] <= 1) { for (int i = 0; i < rev[0].size(); i++) { if (remain[rev[0][i].second] == 0) continue; remain[rev[0][i].second] = 0; outset.erase(outset.find(make_pair(out[rev[0][i].first], rev[0][i].first))); out[rev[0][i].first]--; outset.insert(make_pair(out[rev[0][i].first], rev[0][i].first)); } } while (!outset.empty() && outset.begin()->first == 0) { int v = outset.begin()->second; outset.erase(outset.begin()); for (int i = 0; i < rev[v].size(); i++) { if (remain[rev[v][i].second] == 0) continue; remain[rev[v][i].second] = 0; outset.erase(outset.find(make_pair(out[rev[v][i].first], rev[v][i].first))); out[rev[v][i].first]--; outset.insert(make_pair(out[rev[v][i].first], rev[v][i].first)); } } //for (int i = 0; i < m; i++) cout << remain[i] << "\n"; //cout << "\n"; ch[0] = 1; DFS(0); //for (int i = 0; i < n; i++) cout << ch[i] << " "; //cout << "\n"; if (ans) { int idx = 0; for (int i = 0; i < path1.size(); i++) res.push_back(path1[i]); //res.push_back(-1); while (ch[adj[junc][idx].first] == 1 || remain[adj[junc][idx].second] == 0) idx++; int first = adj[junc][idx].first; ch[first] = 1; ch2[first] = 1; ch2[junc] = 1; path2.push_back(adj[junc][idx].second); path(first); int rev = -1, v = junc; for (int i = 0; i < path2.size(); i++) { if (v == st) { rev = i; break; } v = V[path2[i]]; } for (int i = rev; i < path2.size(); i++) { cycle.push_back(path2[i]); iscycle[V[path2[i]]] = 1; } for (int i = 0; i < cycle.size(); i++) path2.pop_back(); for (int i = 0; i < path2.size(); i++) res.push_back(path2[i]); //res.push_back(-1); for (int i = 0; i < cycle.size(); i++) res.push_back(cycle[i]); //res.push_back(-1); for (int i = path2.size() - 1; i >= 0; i--) res.push_back(path2[i]); //res.push_back(-1); //for (int i = 0; i < n; i++) cout << ch[i] << " "; //cout << "\n"; //for (int i = 0; i < n; i++) cout << iscycle[i] << " "; //cout << "\n"; for (int i = 0; i < n; i++) ch[i] = 0; st = -1; path1.clear(); ch[0] = 1; DFS(0); idx++; while (ch[adj[junc][idx].first] == 1 || remain[adj[junc][idx].second] == 0) idx++; int second = adj[junc][idx].first; ch[second] = 1; path3.push_back(adj[junc][idx].second); check(second); if (isconnect) { int k = 0; for (int i = 0; i < cycle.size(); i++) if (V[cycle[i]] == st) k = i; for (int i = 0; i < path3.size(); i++) res.push_back(path3[i]); //res.push_back(-1); for (int i = k; i >= 0; i--) res.push_back(cycle[i]); //res.push_back(-1); for (int i = cycle.size() - 1; i > k; i--) res.push_back(cycle[i]); //res.push_back(-1); for (int i = path3.size() - 1; i >= 0; i--) res.push_back(path3[i]); //res.push_back(-1); } else { for (int i = 0; i < n; i++) ch[i] = 0; st = -1; path1.clear(); ch[0] = 1; DFS(0); ch[second] = 1; ch2[second] = 1; ch2[junc] = 1; path3.push_back(adj[junc][idx].second); other_path(second); rev = -1; v = junc; for (int i = 0; i < path3.size(); i++) { if (v == other_st) { rev = i; break; } v = V[path3[i]]; } for (int i = rev; i < path3.size(); i++) { cycle2.push_back(path3[i]); } for (int i = 0; i < cycle2.size(); i++) path3.pop_back(); for (int i = 0; i < path3.size(); i++) res.push_back(path3[i]); //res.push_back(-1); for (int i = 0; i < cycle2.size(); i++) res.push_back(cycle2[i]); //res.push_back(-1); for (int i = path3.size() - 1; i >= 0; i--) res.push_back(path3[i]); //res.push_back(-1); for (int i = 0; i < path2.size(); i++) res.push_back(path2[i]); //res.push_back(-1); for (int i = cycle.size() - 1; i >= 0; i--) res.push_back(cycle[i]); //res.push_back(-1); for (int i = path2.size() - 1; i >= 0; i--) res.push_back(path2[i]); //res.push_back(-1); for (int i = 0; i < path3.size(); i++) res.push_back(path3[i]); //res.push_back(-1); for (int i = cycle2.size() - 1; i >= 0; i--) res.push_back(cycle2[i]); //res.push_back(-1); for (int i = path3.size() - 1; i >= 0; i--) res.push_back(path3[i]); //res.push_back(-1); } for (int i = path1.size() - 1; i >= 0; i--) res.push_back(path1[i]); return res; } else return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4948 KB | Output is correct |
2 | Correct | 3 ms | 5076 KB | Output is correct |
3 | Correct | 3 ms | 5076 KB | Output is correct |
4 | Correct | 3 ms | 4948 KB | Output is correct |
5 | Correct | 3 ms | 4948 KB | Output is correct |
6 | Correct | 3 ms | 5076 KB | Output is correct |
7 | Correct | 43 ms | 12208 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5076 KB | Output is correct |
2 | Correct | 3 ms | 5076 KB | Output is correct |
3 | Correct | 3 ms | 5076 KB | Output is correct |
4 | Correct | 3 ms | 5076 KB | Output is correct |
5 | Correct | 3 ms | 5076 KB | Output is correct |
6 | Correct | 37 ms | 11680 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 5332 KB | Output is correct |
2 | Correct | 4 ms | 5072 KB | Output is correct |
3 | Correct | 3 ms | 5076 KB | Output is correct |
4 | Correct | 3 ms | 4948 KB | Output is correct |
5 | Correct | 5 ms | 5204 KB | Output is correct |
6 | Correct | 3 ms | 5076 KB | Output is correct |
7 | Correct | 3 ms | 5192 KB | Output is correct |
8 | Correct | 3 ms | 5076 KB | Output is correct |
9 | Correct | 3 ms | 5076 KB | Output is correct |
10 | Correct | 4 ms | 5204 KB | Output is correct |
11 | Correct | 3 ms | 5076 KB | Output is correct |
12 | Correct | 4 ms | 5204 KB | Output is correct |
13 | Correct | 3 ms | 5044 KB | Output is correct |
14 | Correct | 2 ms | 5076 KB | Output is correct |
15 | Correct | 2 ms | 5076 KB | Output is correct |
16 | Correct | 2 ms | 5076 KB | Output is correct |
17 | Correct | 24 ms | 9308 KB | Output is correct |
18 | Correct | 20 ms | 8908 KB | Output is correct |
19 | Correct | 3 ms | 5076 KB | Output is correct |
20 | Correct | 3 ms | 5076 KB | Output is correct |
21 | Correct | 3 ms | 5076 KB | Output is correct |
22 | Correct | 3 ms | 5076 KB | Output is correct |
23 | Correct | 35 ms | 11724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5076 KB | Output is correct |
2 | Correct | 4 ms | 5204 KB | Output is correct |
3 | Correct | 52 ms | 12300 KB | Output is correct |
4 | Correct | 70 ms | 12744 KB | Output is correct |
5 | Correct | 4 ms | 5204 KB | Output is correct |
6 | Correct | 4 ms | 5204 KB | Output is correct |
7 | Correct | 3 ms | 4948 KB | Output is correct |
8 | Correct | 3 ms | 4948 KB | Output is correct |
9 | Correct | 4 ms | 4948 KB | Output is correct |
10 | Correct | 4 ms | 5332 KB | Output is correct |
11 | Correct | 5 ms | 5300 KB | Output is correct |
12 | Correct | 5 ms | 5204 KB | Output is correct |
13 | Correct | 4 ms | 5332 KB | Output is correct |
14 | Correct | 4 ms | 5204 KB | Output is correct |
15 | Correct | 4 ms | 5332 KB | Output is correct |
16 | Correct | 4 ms | 5204 KB | Output is correct |
17 | Correct | 4 ms | 5076 KB | Output is correct |
18 | Correct | 4 ms | 5204 KB | Output is correct |
19 | Correct | 4 ms | 5204 KB | Output is correct |
20 | Correct | 59 ms | 13552 KB | Output is correct |
21 | Correct | 74 ms | 13028 KB | Output is correct |
22 | Correct | 4 ms | 5204 KB | Output is correct |
23 | Correct | 3 ms | 5076 KB | Output is correct |
24 | Correct | 3 ms | 5076 KB | Output is correct |
25 | Correct | 3 ms | 5076 KB | Output is correct |
26 | Correct | 4 ms | 5332 KB | Output is correct |
27 | Correct | 66 ms | 13072 KB | Output is correct |
28 | Correct | 67 ms | 13260 KB | Output is correct |
29 | Correct | 3 ms | 5076 KB | Output is correct |
30 | Correct | 85 ms | 14380 KB | Output is correct |
31 | Correct | 3 ms | 5076 KB | Output is correct |
32 | Correct | 66 ms | 13136 KB | Output is correct |
33 | Correct | 57 ms | 12848 KB | Output is correct |
34 | Correct | 24 ms | 9308 KB | Output is correct |
35 | Correct | 4 ms | 5204 KB | Output is correct |
36 | Correct | 62 ms | 12068 KB | Output is correct |
37 | Correct | 56 ms | 13936 KB | Output is correct |
38 | Correct | 3 ms | 5076 KB | Output is correct |
39 | Correct | 60 ms | 12236 KB | Output is correct |
40 | Correct | 3 ms | 5204 KB | Output is correct |
41 | Correct | 86 ms | 14380 KB | Output is correct |
42 | Correct | 71 ms | 13388 KB | Output is correct |
43 | Correct | 3 ms | 5076 KB | Output is correct |
44 | Correct | 4 ms | 5204 KB | Output is correct |
45 | Correct | 3 ms | 5332 KB | Output is correct |
46 | Correct | 20 ms | 8776 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4948 KB | Output is correct |
2 | Correct | 3 ms | 5076 KB | Output is correct |
3 | Correct | 3 ms | 5076 KB | Output is correct |
4 | Correct | 3 ms | 4948 KB | Output is correct |
5 | Correct | 3 ms | 4948 KB | Output is correct |
6 | Correct | 3 ms | 5076 KB | Output is correct |
7 | Correct | 43 ms | 12208 KB | Output is correct |
8 | Correct | 3 ms | 5076 KB | Output is correct |
9 | Correct | 3 ms | 5076 KB | Output is correct |
10 | Correct | 3 ms | 5076 KB | Output is correct |
11 | Correct | 3 ms | 5076 KB | Output is correct |
12 | Correct | 3 ms | 5076 KB | Output is correct |
13 | Correct | 37 ms | 11680 KB | Output is correct |
14 | Correct | 4 ms | 5332 KB | Output is correct |
15 | Correct | 4 ms | 5072 KB | Output is correct |
16 | Correct | 3 ms | 5076 KB | Output is correct |
17 | Correct | 3 ms | 4948 KB | Output is correct |
18 | Correct | 5 ms | 5204 KB | Output is correct |
19 | Correct | 3 ms | 5076 KB | Output is correct |
20 | Correct | 3 ms | 5192 KB | Output is correct |
21 | Correct | 3 ms | 5076 KB | Output is correct |
22 | Correct | 3 ms | 5076 KB | Output is correct |
23 | Correct | 4 ms | 5204 KB | Output is correct |
24 | Correct | 3 ms | 5076 KB | Output is correct |
25 | Correct | 4 ms | 5204 KB | Output is correct |
26 | Correct | 3 ms | 5044 KB | Output is correct |
27 | Correct | 2 ms | 5076 KB | Output is correct |
28 | Correct | 2 ms | 5076 KB | Output is correct |
29 | Correct | 2 ms | 5076 KB | Output is correct |
30 | Correct | 24 ms | 9308 KB | Output is correct |
31 | Correct | 20 ms | 8908 KB | Output is correct |
32 | Correct | 3 ms | 5076 KB | Output is correct |
33 | Correct | 3 ms | 5076 KB | Output is correct |
34 | Correct | 3 ms | 5076 KB | Output is correct |
35 | Correct | 3 ms | 5076 KB | Output is correct |
36 | Correct | 35 ms | 11724 KB | Output is correct |
37 | Correct | 3 ms | 5076 KB | Output is correct |
38 | Correct | 3 ms | 5076 KB | Output is correct |
39 | Correct | 3 ms | 5076 KB | Output is correct |
40 | Correct | 3 ms | 5076 KB | Output is correct |
41 | Correct | 33 ms | 8728 KB | Output is correct |
42 | Correct | 5 ms | 5332 KB | Output is correct |
43 | Correct | 72 ms | 13292 KB | Output is correct |
44 | Correct | 74 ms | 13288 KB | Output is correct |
45 | Correct | 77 ms | 13416 KB | Output is correct |
46 | Correct | 3 ms | 4948 KB | Output is correct |
47 | Correct | 3 ms | 5076 KB | Output is correct |
48 | Correct | 3 ms | 5076 KB | Output is correct |
49 | Correct | 4 ms | 5204 KB | Output is correct |
50 | Correct | 134 ms | 26844 KB | Output is correct |
51 | Correct | 178 ms | 21512 KB | Output is correct |
52 | Correct | 181 ms | 21768 KB | Output is correct |
53 | Correct | 180 ms | 22352 KB | Output is correct |
54 | Correct | 176 ms | 21472 KB | Output is correct |
55 | Correct | 182 ms | 21412 KB | Output is correct |
56 | Correct | 206 ms | 21840 KB | Output is correct |
57 | Correct | 75 ms | 18228 KB | Output is correct |
58 | Correct | 129 ms | 25608 KB | Output is correct |
59 | Correct | 240 ms | 21380 KB | Output is correct |
60 | Correct | 203 ms | 21484 KB | Output is correct |
61 | Correct | 294 ms | 21128 KB | Output is correct |
62 | Correct | 37 ms | 9592 KB | Output is correct |
63 | Correct | 157 ms | 20812 KB | Output is correct |
64 | Correct | 48 ms | 9788 KB | Output is correct |
65 | Correct | 2 ms | 5076 KB | Output is correct |
66 | Correct | 3 ms | 5128 KB | Output is correct |
67 | Correct | 152 ms | 22288 KB | Output is correct |
68 | Correct | 107 ms | 14432 KB | Output is correct |
69 | Correct | 142 ms | 16844 KB | Output is correct |
70 | Correct | 4 ms | 5332 KB | Output is correct |
71 | Correct | 163 ms | 15468 KB | Output is correct |
72 | Correct | 3 ms | 5076 KB | Output is correct |
73 | Correct | 210 ms | 19216 KB | Output is correct |
74 | Correct | 122 ms | 26788 KB | Output is correct |
75 | Correct | 9 ms | 5716 KB | Output is correct |
76 | Correct | 50 ms | 15120 KB | Output is correct |
77 | Correct | 110 ms | 24320 KB | Output is correct |
78 | Correct | 231 ms | 21612 KB | Output is correct |
79 | Correct | 3 ms | 5076 KB | Output is correct |
80 | Correct | 221 ms | 26144 KB | Output is correct |
81 | Correct | 4 ms | 5204 KB | Output is correct |
82 | Correct | 50 ms | 12712 KB | Output is correct |
83 | Correct | 3 ms | 5204 KB | Output is correct |
84 | Correct | 3 ms | 4948 KB | Output is correct |
85 | Correct | 56 ms | 15192 KB | Output is correct |
86 | Correct | 4 ms | 5212 KB | Output is correct |
87 | Correct | 18 ms | 9444 KB | Output is correct |
88 | Correct | 6 ms | 5460 KB | Output is correct |
89 | Correct | 213 ms | 21492 KB | Output is correct |
90 | Correct | 255 ms | 21204 KB | Output is correct |
91 | Correct | 206 ms | 26596 KB | Output is correct |
92 | Correct | 3 ms | 5076 KB | Output is correct |