#pragma once
#include <variant>
#include <bits/stdc++.h>
using namespace std;
#define MX 200000
bool dead[MX]{};
multiset<pair<int,int>> adj[MX];
vector<pair<int,int>> rev[MX];
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
//we should delete dead ends! just bc its fun!
for (int i = 0; i < M; i++) {
adj[U[i]].insert({ V[i], i });
rev[V[i]].push_back({ U[i], i });
}
vector<int> del;
for (int i = 0; i < N; i++) {
if (!adj[i].size()) del.push_back(i);
}
auto machine = [&]() {
while (del.size()) {
int i = del.back(); del.pop_back();
if (dead[i]) continue;
dead[i] = 1;
for (auto& x : rev[i]) {
adj[x.first].erase({ i, x.second });
if (!adj[x.first].size()) del.push_back(x.first);
}
}
};
machine();
int i = 0;
vector<int> initial_path;
while (1) {
if (dead[i]) return false;
if (adj[i].size() >= 2) break;
int t = i;
initial_path.push_back(adj[i].begin()->second);
i = adj[i].begin()->first;
del.push_back(t);
machine();
}
//35%
auto [a, pa] = *adj[i].begin();
auto [b, pb] = *adj[i].rbegin();
//find the loops of a and b
bool vis[MX] = {}; vis[i] = 1;
vector<int> la = {pa};
while (!vis[a]) {
vis[a] = 1;
la.push_back(adj[a].begin()->second);
a = adj[a].begin()->first;
}
auto lpa = la.begin();
if (a != i) lpa = find(la.begin(), la.end(), adj[a].begin()->second);
//document a's cycle
bool visa[MX] = {};
while (!visa[a]) {
visa[a] = 1;
a = adj[a].begin()->first;
}
bool vis2[MX] = {}; vis2[i] = 1;
vector<int> lb = { pb };
while (!visa[b] && !vis2[b]) {
vis2[b] = 1;
lb.push_back(adj[b].begin()->second);
b = adj[b].begin()->first;
}
auto lpb = lb.begin();
if (visa[b]) lpb = find(la.begin(), la.end(), adj[b].begin()->second);
else if (b != i) lpb = find(lb.begin(), lb.end(), adj[b].begin()->second);
// build the answer
std::vector<int>::iterator owo;
vector<int> ans;
ans.insert(ans.end(), initial_path.begin(), initial_path.end());
if (visa[b]) {
//case 1: same loop
//loop a
ans.insert(ans.end(), la.begin(), la.end());
vector<int> t = { la.begin(), lpa };
ans.insert(ans.end(), t.rbegin(), t.rend());
//loop b
ans.insert(ans.end(), lb.begin(), lb.end());
t = { lpb, la.end() };
t.insert(t.end(), lpa, lpb);
ans.insert(ans.end(), t.rbegin(), t.rend());
ans.insert(ans.end(), lb.rbegin(), lb.rend());
}
else {
//case 2: diff loop
//loop a
ans.insert(ans.end(), la.begin(), la.end());
vector<int> t = { la.begin(), lpa };
ans.insert(ans.end(), t.rbegin(), t.rend());
//loop b
ans.insert(ans.end(), lb.begin(), lb.end());
t = { lb.begin(), lpb };
ans.insert(ans.end(), t.rbegin(), t.rend());
//loop a
ans.insert(ans.end(), la.begin(), lpa);
t = { lpa, la.end() };
ans.insert(ans.end(), t.rbegin(), t.rend());
t = { la.begin(), lpa };
ans.insert(ans.end(), t.rbegin(), t.rend());
//loop b
ans.insert(ans.end(), lb.begin(), lpb);
t = { lpb, lb.end() };
ans.insert(ans.end(), t.rbegin(), t.rend());
t = { lb.begin(), lpb };
ans.insert(ans.end(), t.rbegin(), t.rend());
}
ans.insert(ans.end(), initial_path.rbegin(), initial_path.rend());
return ans;
}
//int main() {
// auto x = find_journey(2, 3, { 0, 0, 1}, { 1, 1, 0 });
// for (auto& i : get<vector<int>>(x)) cout << i << endl;
//}
Compilation message
islands.cpp:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14932 KB |
Output is correct |
2 |
Correct |
8 ms |
14932 KB |
Output is correct |
3 |
Correct |
8 ms |
14900 KB |
Output is correct |
4 |
Correct |
7 ms |
14932 KB |
Output is correct |
5 |
Correct |
7 ms |
14932 KB |
Output is correct |
6 |
Correct |
7 ms |
14932 KB |
Output is correct |
7 |
Correct |
57 ms |
29760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14932 KB |
Output is correct |
2 |
Correct |
6 ms |
14932 KB |
Output is correct |
3 |
Correct |
6 ms |
14904 KB |
Output is correct |
4 |
Correct |
7 ms |
14912 KB |
Output is correct |
5 |
Correct |
8 ms |
14932 KB |
Output is correct |
6 |
Correct |
68 ms |
27672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15316 KB |
Output is correct |
2 |
Correct |
7 ms |
14924 KB |
Output is correct |
3 |
Correct |
7 ms |
14932 KB |
Output is correct |
4 |
Correct |
6 ms |
14932 KB |
Output is correct |
5 |
Correct |
8 ms |
15052 KB |
Output is correct |
6 |
Correct |
7 ms |
14932 KB |
Output is correct |
7 |
Correct |
7 ms |
15060 KB |
Output is correct |
8 |
Correct |
7 ms |
14900 KB |
Output is correct |
9 |
Correct |
7 ms |
14932 KB |
Output is correct |
10 |
Correct |
8 ms |
15060 KB |
Output is correct |
11 |
Correct |
6 ms |
14904 KB |
Output is correct |
12 |
Correct |
10 ms |
15168 KB |
Output is correct |
13 |
Correct |
7 ms |
14932 KB |
Output is correct |
14 |
Correct |
7 ms |
14912 KB |
Output is correct |
15 |
Correct |
6 ms |
14932 KB |
Output is correct |
16 |
Correct |
7 ms |
14932 KB |
Output is correct |
17 |
Correct |
41 ms |
22988 KB |
Output is correct |
18 |
Correct |
34 ms |
21580 KB |
Output is correct |
19 |
Correct |
7 ms |
14904 KB |
Output is correct |
20 |
Correct |
7 ms |
14872 KB |
Output is correct |
21 |
Correct |
7 ms |
14932 KB |
Output is correct |
22 |
Correct |
7 ms |
14932 KB |
Output is correct |
23 |
Correct |
68 ms |
27724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14932 KB |
Output is correct |
2 |
Correct |
8 ms |
15188 KB |
Output is correct |
3 |
Correct |
86 ms |
28852 KB |
Output is correct |
4 |
Correct |
85 ms |
29432 KB |
Output is correct |
5 |
Correct |
8 ms |
15188 KB |
Output is correct |
6 |
Correct |
10 ms |
15316 KB |
Output is correct |
7 |
Correct |
7 ms |
14908 KB |
Output is correct |
8 |
Correct |
7 ms |
14916 KB |
Output is correct |
9 |
Correct |
6 ms |
14932 KB |
Output is correct |
10 |
Correct |
7 ms |
15100 KB |
Output is correct |
11 |
Correct |
8 ms |
15304 KB |
Output is correct |
12 |
Correct |
8 ms |
15216 KB |
Output is correct |
13 |
Correct |
8 ms |
15316 KB |
Output is correct |
14 |
Correct |
10 ms |
15304 KB |
Output is correct |
15 |
Correct |
9 ms |
15384 KB |
Output is correct |
16 |
Correct |
7 ms |
15052 KB |
Output is correct |
17 |
Correct |
7 ms |
14908 KB |
Output is correct |
18 |
Correct |
8 ms |
15296 KB |
Output is correct |
19 |
Correct |
7 ms |
15060 KB |
Output is correct |
20 |
Correct |
97 ms |
30484 KB |
Output is correct |
21 |
Correct |
85 ms |
29772 KB |
Output is correct |
22 |
Correct |
7 ms |
15060 KB |
Output is correct |
23 |
Correct |
7 ms |
14984 KB |
Output is correct |
24 |
Correct |
7 ms |
14900 KB |
Output is correct |
25 |
Correct |
9 ms |
15092 KB |
Output is correct |
26 |
Correct |
7 ms |
15188 KB |
Output is correct |
27 |
Correct |
87 ms |
30076 KB |
Output is correct |
28 |
Correct |
87 ms |
30212 KB |
Output is correct |
29 |
Correct |
7 ms |
14932 KB |
Output is correct |
30 |
Correct |
93 ms |
31264 KB |
Output is correct |
31 |
Correct |
7 ms |
14932 KB |
Output is correct |
32 |
Correct |
87 ms |
29744 KB |
Output is correct |
33 |
Correct |
91 ms |
29688 KB |
Output is correct |
34 |
Correct |
37 ms |
22980 KB |
Output is correct |
35 |
Correct |
7 ms |
15048 KB |
Output is correct |
36 |
Correct |
71 ms |
28024 KB |
Output is correct |
37 |
Correct |
80 ms |
30464 KB |
Output is correct |
38 |
Correct |
7 ms |
15060 KB |
Output is correct |
39 |
Correct |
76 ms |
27500 KB |
Output is correct |
40 |
Correct |
7 ms |
15060 KB |
Output is correct |
41 |
Correct |
95 ms |
31312 KB |
Output is correct |
42 |
Correct |
86 ms |
30272 KB |
Output is correct |
43 |
Correct |
7 ms |
14932 KB |
Output is correct |
44 |
Correct |
8 ms |
15228 KB |
Output is correct |
45 |
Correct |
7 ms |
15156 KB |
Output is correct |
46 |
Correct |
32 ms |
21568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14932 KB |
Output is correct |
2 |
Correct |
8 ms |
14932 KB |
Output is correct |
3 |
Correct |
8 ms |
14900 KB |
Output is correct |
4 |
Correct |
7 ms |
14932 KB |
Output is correct |
5 |
Correct |
7 ms |
14932 KB |
Output is correct |
6 |
Correct |
7 ms |
14932 KB |
Output is correct |
7 |
Correct |
57 ms |
29760 KB |
Output is correct |
8 |
Correct |
7 ms |
14932 KB |
Output is correct |
9 |
Correct |
6 ms |
14932 KB |
Output is correct |
10 |
Correct |
6 ms |
14904 KB |
Output is correct |
11 |
Correct |
7 ms |
14912 KB |
Output is correct |
12 |
Correct |
8 ms |
14932 KB |
Output is correct |
13 |
Correct |
68 ms |
27672 KB |
Output is correct |
14 |
Correct |
8 ms |
15316 KB |
Output is correct |
15 |
Correct |
7 ms |
14924 KB |
Output is correct |
16 |
Correct |
7 ms |
14932 KB |
Output is correct |
17 |
Correct |
6 ms |
14932 KB |
Output is correct |
18 |
Correct |
8 ms |
15052 KB |
Output is correct |
19 |
Correct |
7 ms |
14932 KB |
Output is correct |
20 |
Correct |
7 ms |
15060 KB |
Output is correct |
21 |
Correct |
7 ms |
14900 KB |
Output is correct |
22 |
Correct |
7 ms |
14932 KB |
Output is correct |
23 |
Correct |
8 ms |
15060 KB |
Output is correct |
24 |
Correct |
6 ms |
14904 KB |
Output is correct |
25 |
Correct |
10 ms |
15168 KB |
Output is correct |
26 |
Correct |
7 ms |
14932 KB |
Output is correct |
27 |
Correct |
7 ms |
14912 KB |
Output is correct |
28 |
Correct |
6 ms |
14932 KB |
Output is correct |
29 |
Correct |
7 ms |
14932 KB |
Output is correct |
30 |
Correct |
41 ms |
22988 KB |
Output is correct |
31 |
Correct |
34 ms |
21580 KB |
Output is correct |
32 |
Correct |
7 ms |
14904 KB |
Output is correct |
33 |
Correct |
7 ms |
14872 KB |
Output is correct |
34 |
Correct |
7 ms |
14932 KB |
Output is correct |
35 |
Correct |
7 ms |
14932 KB |
Output is correct |
36 |
Correct |
68 ms |
27724 KB |
Output is correct |
37 |
Correct |
7 ms |
14904 KB |
Output is correct |
38 |
Correct |
6 ms |
14976 KB |
Output is correct |
39 |
Correct |
7 ms |
14908 KB |
Output is correct |
40 |
Correct |
7 ms |
15060 KB |
Output is correct |
41 |
Correct |
50 ms |
21760 KB |
Output is correct |
42 |
Correct |
9 ms |
15308 KB |
Output is correct |
43 |
Correct |
63 ms |
23996 KB |
Output is correct |
44 |
Correct |
62 ms |
23976 KB |
Output is correct |
45 |
Correct |
61 ms |
23992 KB |
Output is correct |
46 |
Correct |
7 ms |
14896 KB |
Output is correct |
47 |
Correct |
7 ms |
14912 KB |
Output is correct |
48 |
Correct |
7 ms |
14952 KB |
Output is correct |
49 |
Correct |
7 ms |
15108 KB |
Output is correct |
50 |
Correct |
90 ms |
28120 KB |
Output is correct |
51 |
Correct |
145 ms |
32656 KB |
Output is correct |
52 |
Correct |
156 ms |
32584 KB |
Output is correct |
53 |
Correct |
155 ms |
32552 KB |
Output is correct |
54 |
Correct |
147 ms |
33060 KB |
Output is correct |
55 |
Correct |
161 ms |
32980 KB |
Output is correct |
56 |
Correct |
161 ms |
33056 KB |
Output is correct |
57 |
Correct |
99 ms |
31948 KB |
Output is correct |
58 |
Correct |
84 ms |
27644 KB |
Output is correct |
59 |
Correct |
126 ms |
33752 KB |
Output is correct |
60 |
Correct |
119 ms |
33484 KB |
Output is correct |
61 |
Correct |
123 ms |
33484 KB |
Output is correct |
62 |
Correct |
26 ms |
18288 KB |
Output is correct |
63 |
Correct |
95 ms |
32532 KB |
Output is correct |
64 |
Correct |
54 ms |
23328 KB |
Output is correct |
65 |
Correct |
7 ms |
14932 KB |
Output is correct |
66 |
Correct |
6 ms |
15060 KB |
Output is correct |
67 |
Correct |
95 ms |
33488 KB |
Output is correct |
68 |
Correct |
106 ms |
31308 KB |
Output is correct |
69 |
Correct |
53 ms |
25040 KB |
Output is correct |
70 |
Correct |
7 ms |
15188 KB |
Output is correct |
71 |
Correct |
75 ms |
28732 KB |
Output is correct |
72 |
Correct |
7 ms |
14932 KB |
Output is correct |
73 |
Correct |
115 ms |
33224 KB |
Output is correct |
74 |
Correct |
85 ms |
27880 KB |
Output is correct |
75 |
Correct |
11 ms |
15828 KB |
Output is correct |
76 |
Correct |
35 ms |
21072 KB |
Output is correct |
77 |
Correct |
50 ms |
25556 KB |
Output is correct |
78 |
Correct |
132 ms |
33480 KB |
Output is correct |
79 |
Correct |
7 ms |
14932 KB |
Output is correct |
80 |
Correct |
167 ms |
35008 KB |
Output is correct |
81 |
Correct |
7 ms |
15040 KB |
Output is correct |
82 |
Correct |
88 ms |
29772 KB |
Output is correct |
83 |
Correct |
7 ms |
15060 KB |
Output is correct |
84 |
Correct |
6 ms |
14932 KB |
Output is correct |
85 |
Correct |
37 ms |
21108 KB |
Output is correct |
86 |
Correct |
7 ms |
15176 KB |
Output is correct |
87 |
Correct |
8 ms |
15828 KB |
Output is correct |
88 |
Correct |
9 ms |
15500 KB |
Output is correct |
89 |
Correct |
119 ms |
33348 KB |
Output is correct |
90 |
Correct |
123 ms |
33488 KB |
Output is correct |
91 |
Correct |
137 ms |
34520 KB |
Output is correct |
92 |
Correct |
9 ms |
14932 KB |
Output is correct |