// correct/solution-ayaze-full.cpp
#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
vector<set<pair<int, int>>> adj_list, rev_adj_list;
queue<int> unprocessed_zero_outdeg;
void RemoveNode(int v) {
for (auto [u, edge_idx] : adj_list[v]) {
rev_adj_list[u].erase({v, edge_idx});
}
for (auto [u, edge_idx] : rev_adj_list[v]) {
adj_list[u].erase({v, edge_idx});
if (adj_list[u].empty()) {
unprocessed_zero_outdeg.push(u);
}
}
adj_list[v].clear();
rev_adj_list[v].clear();
}
// nodes, edge idxs
// last node is the first cyclic node
pair<vector<int>, vector<int>> FindCycle(int u, bool take_second) {
auto it = adj_list[u].begin();
if (take_second) ++it;
set<int> seen = {u};
vector<int> nodes = {u};
vector<int> edge_idxs = {};
auto [v, edge_idx] = *it;
while (!seen.count(v)) {
nodes.push_back(v);
edge_idxs.push_back(edge_idx);
seen.insert(v);
edge_idx = adj_list[v].begin()->second;
v = adj_list[v].begin()->first;
}
nodes.push_back(v);
edge_idxs.push_back(edge_idx);
return {nodes, edge_idxs};
}
pair<vector<int>, vector<int>> ConstructSimpleCycle(vector<int> nodes, vector<int> edge_idxs) {
int first_occ = -1;
for (int i = 0 ; i+1 < static_cast<int>(nodes.size()) ; i++) {
if (nodes[i] == nodes.back()) {
first_occ = i;
break;
}
}
vector<int> first_path;
for (int i = 0 ; i < static_cast<int>(edge_idxs.size()) ; i++) {
first_path.push_back(edge_idxs[i]);
}
for (int i = first_occ-1 ; i >= 0 ; i--) {
first_path.push_back(edge_idxs[i]);
}
vector<int> second_path;
for (int i = 0 ; i < first_occ ; i++) {
second_path.push_back(edge_idxs[i]);
}
for (int i = static_cast<int>(edge_idxs.size())-1 ; i >= 0 ; i--) {
second_path.push_back(edge_idxs[i]);
}
return {first_path, second_path};
}
void FindTour(int u, vector<int> &ans) {
while (!unprocessed_zero_outdeg.empty()) {
int v = unprocessed_zero_outdeg.front();
unprocessed_zero_outdeg.pop();
RemoveNode(v);
}
if (adj_list[u].empty()) {
ans.push_back(-1);
return;
}
if (static_cast<int>(adj_list[u].size()) == 1) {
auto [v, edge_idx] = *adj_list[u].begin();
ans.push_back(edge_idx);
RemoveNode(u);
FindTour(v, ans);
ans.push_back(edge_idx);
return;
}
auto [first_cycle, first_cycle_edges] = FindCycle(u, false);
auto [second_cycle, second_cycle_edges] = FindCycle(u, true);
map<int, int> first_occ;
for (int i = 0 ; i+1 < static_cast<int>(first_cycle.size()) ; i++) {
first_occ[first_cycle[i]] = i;
}
int common_node = -1;
int first_common_occ = -1;
int second_common_occ = -1;
for (int i = 1 ; i+1 < static_cast<int>(second_cycle.size()) ; i++) {
if (first_occ.count(second_cycle[i])) {
common_node = second_cycle[i];
second_common_occ = i;
first_common_occ = first_occ[common_node];
break;
}
}
if (common_node == -1) { // two disjoint cycles
auto cycle1 = ConstructSimpleCycle(first_cycle, first_cycle_edges);
auto cycle2 = ConstructSimpleCycle(second_cycle, second_cycle_edges);
ans.insert(ans.end(), cycle1.first.begin(), cycle1.first.end());
ans.insert(ans.end(), cycle2.first.begin(), cycle2.first.end());
ans.insert(ans.end(), cycle1.second.begin(), cycle1.second.end());
ans.insert(ans.end(), cycle2.second.begin(), cycle2.second.end());
return;
}
int first_cyclic_occ = -1;
for (int i = 0 ; i+1 < static_cast<int>(first_cycle.size()) ; i++) {
if (first_cycle[i] == first_cycle.back()) {
first_cyclic_occ = i;
break;
}
}
// loop the first path
for (int i = 0 ; i < static_cast<int>(first_cycle_edges.size()) ; i++) {
ans.push_back(first_cycle_edges[i]);
}
for (int i = first_cyclic_occ-1 ; i >= 0 ; i--) {
ans.push_back(first_cycle_edges[i]);
}
// enter first path through second path
for (int i = 0 ; i < second_common_occ ; i++) {
ans.push_back(second_cycle_edges[i]);
}
// only one of the following loops will be executed; we want
// to reach the start of the cycle
for (int i = first_common_occ-1 ; i >= first_cyclic_occ ; i--) {
ans.push_back(first_cycle_edges[i]);
}
for (int i = first_common_occ ; i < first_cyclic_occ ; i++) {
ans.push_back(first_cycle_edges[i]);
}
// go back through the latter part of first path and second path
for (int i = static_cast<int>(first_cycle_edges.size())-1 ; i >= first_common_occ ; i--) {
ans.push_back(first_cycle_edges[i]);
}
for (int i = second_common_occ-1 ; i >= 0 ; i--) {
ans.push_back(second_cycle_edges[i]);
}
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
adj_list.resize(N);
rev_adj_list.resize(N);
for (int i = 0 ; i < M ; i++) {
adj_list[U[i]].insert({V[i], i});
rev_adj_list[V[i]].insert({U[i], i});
}
for (int i = 0 ; i < N ; i++) {
if (adj_list[i].empty()) {
unprocessed_zero_outdeg.push(i);
}
}
vector<int> ret;
FindTour(0, ret);
for (int e : ret) {
if (e == -1) {
return false;
}
}
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
124 ms |
22116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
151 ms |
17796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
3 ms |
980 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
136 ms |
11324 KB |
Output is correct |
18 |
Correct |
77 ms |
9104 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
159 ms |
17740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
724 KB |
Output is correct |
3 |
Correct |
223 ms |
20028 KB |
Output is correct |
4 |
Correct |
228 ms |
20124 KB |
Output is correct |
5 |
Correct |
3 ms |
784 KB |
Output is correct |
6 |
Correct |
3 ms |
724 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
4 ms |
712 KB |
Output is correct |
12 |
Correct |
4 ms |
724 KB |
Output is correct |
13 |
Correct |
4 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
852 KB |
Output is correct |
15 |
Correct |
9 ms |
980 KB |
Output is correct |
16 |
Correct |
2 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
2 ms |
724 KB |
Output is correct |
19 |
Correct |
2 ms |
596 KB |
Output is correct |
20 |
Correct |
274 ms |
22192 KB |
Output is correct |
21 |
Correct |
230 ms |
20012 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
2 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
596 KB |
Output is correct |
27 |
Correct |
262 ms |
21124 KB |
Output is correct |
28 |
Correct |
285 ms |
21160 KB |
Output is correct |
29 |
Correct |
1 ms |
256 KB |
Output is correct |
30 |
Correct |
298 ms |
22300 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
224 ms |
20004 KB |
Output is correct |
33 |
Correct |
241 ms |
21132 KB |
Output is correct |
34 |
Correct |
87 ms |
11332 KB |
Output is correct |
35 |
Correct |
1 ms |
468 KB |
Output is correct |
36 |
Correct |
203 ms |
17932 KB |
Output is correct |
37 |
Correct |
217 ms |
21104 KB |
Output is correct |
38 |
Correct |
1 ms |
468 KB |
Output is correct |
39 |
Correct |
181 ms |
17224 KB |
Output is correct |
40 |
Correct |
2 ms |
592 KB |
Output is correct |
41 |
Correct |
212 ms |
22204 KB |
Output is correct |
42 |
Correct |
297 ms |
21112 KB |
Output is correct |
43 |
Correct |
1 ms |
212 KB |
Output is correct |
44 |
Correct |
3 ms |
724 KB |
Output is correct |
45 |
Correct |
4 ms |
596 KB |
Output is correct |
46 |
Correct |
81 ms |
9060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
124 ms |
22116 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
151 ms |
17796 KB |
Output is correct |
14 |
Correct |
4 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
3 ms |
980 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
2 ms |
724 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
2 ms |
852 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
136 ms |
11324 KB |
Output is correct |
31 |
Correct |
77 ms |
9104 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
159 ms |
17740 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
1 ms |
212 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
111 ms |
10096 KB |
Output is correct |
42 |
Correct |
4 ms |
852 KB |
Output is correct |
43 |
Correct |
135 ms |
15996 KB |
Output is correct |
44 |
Correct |
117 ms |
15992 KB |
Output is correct |
45 |
Correct |
148 ms |
16076 KB |
Output is correct |
46 |
Correct |
1 ms |
212 KB |
Output is correct |
47 |
Correct |
1 ms |
212 KB |
Output is correct |
48 |
Correct |
1 ms |
212 KB |
Output is correct |
49 |
Correct |
5 ms |
724 KB |
Output is correct |
50 |
Correct |
288 ms |
44136 KB |
Output is correct |
51 |
Correct |
367 ms |
31668 KB |
Output is correct |
52 |
Correct |
322 ms |
31660 KB |
Output is correct |
53 |
Correct |
331 ms |
31652 KB |
Output is correct |
54 |
Correct |
365 ms |
31616 KB |
Output is correct |
55 |
Correct |
332 ms |
31616 KB |
Output is correct |
56 |
Correct |
358 ms |
31504 KB |
Output is correct |
57 |
Correct |
276 ms |
27732 KB |
Output is correct |
58 |
Correct |
240 ms |
26300 KB |
Output is correct |
59 |
Correct |
327 ms |
31736 KB |
Output is correct |
60 |
Correct |
345 ms |
31840 KB |
Output is correct |
61 |
Correct |
270 ms |
31720 KB |
Output is correct |
62 |
Correct |
33 ms |
8076 KB |
Output is correct |
63 |
Correct |
205 ms |
30380 KB |
Output is correct |
64 |
Correct |
142 ms |
11416 KB |
Output is correct |
65 |
Correct |
0 ms |
212 KB |
Output is correct |
66 |
Correct |
1 ms |
340 KB |
Output is correct |
67 |
Correct |
216 ms |
31664 KB |
Output is correct |
68 |
Correct |
394 ms |
22312 KB |
Output is correct |
69 |
Correct |
143 ms |
20804 KB |
Output is correct |
70 |
Correct |
2 ms |
596 KB |
Output is correct |
71 |
Correct |
214 ms |
21468 KB |
Output is correct |
72 |
Correct |
0 ms |
212 KB |
Output is correct |
73 |
Correct |
336 ms |
28812 KB |
Output is correct |
74 |
Correct |
244 ms |
28744 KB |
Output is correct |
75 |
Correct |
8 ms |
1492 KB |
Output is correct |
76 |
Correct |
90 ms |
12528 KB |
Output is correct |
77 |
Correct |
113 ms |
21960 KB |
Output is correct |
78 |
Correct |
353 ms |
31808 KB |
Output is correct |
79 |
Correct |
1 ms |
212 KB |
Output is correct |
80 |
Correct |
392 ms |
33748 KB |
Output is correct |
81 |
Correct |
4 ms |
468 KB |
Output is correct |
82 |
Correct |
235 ms |
22220 KB |
Output is correct |
83 |
Correct |
1 ms |
468 KB |
Output is correct |
84 |
Correct |
1 ms |
212 KB |
Output is correct |
85 |
Correct |
89 ms |
13044 KB |
Output is correct |
86 |
Correct |
2 ms |
596 KB |
Output is correct |
87 |
Correct |
7 ms |
8148 KB |
Output is correct |
88 |
Correct |
4 ms |
980 KB |
Output is correct |
89 |
Correct |
336 ms |
32016 KB |
Output is correct |
90 |
Correct |
278 ms |
31728 KB |
Output is correct |
91 |
Correct |
425 ms |
33604 KB |
Output is correct |
92 |
Correct |
0 ms |
212 KB |
Output is correct |