#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int, int> E[200200];
set<pair<int, int>> adj[100100], INV[100100];
vector<int> deg0, ansf, ansb;
int n, s, on[100100], visited[100100], cyc[200200];
bool flag = 0;
vector<int> operator + (const vector<int> &a, const vector<int> &b){
vector<int> ret = a;
for (auto &x:b) ret.push_back(x);
return ret;
}
vector<int> rev(vector<int> a){reverse(a.begin(), a.end()); return a;}
void pop(int x){
auto [v, i] = *adj[x].begin();
adj[x].erase(adj[x].begin());
INV[v].erase(INV[v].find(make_pair(x, i)));
}
void _erase(int x){
if (!on[x]) return;
on[x] = 0;
for (auto &[v, i]:INV[x]){
adj[v].erase(adj[v].find(make_pair(x, i)));
if (adj[v].empty()) deg0.push_back(v);
}
for (auto &[v, i]:adj[x]) INV[v].erase(INV[v].find(make_pair(x, i)));
}
void flip(int i){
auto [u, v] = E[i];
adj[u].erase(adj[u].find(make_pair(v, i))); INV[u].emplace(v, i);
INV[v].erase(INV[v].find(make_pair(u, i))); adj[v].emplace(u, i);
swap(E[i].first, E[i].second);
}
pair<vector<int>, vector<int>> solve(int is, int typ){
int cur = E[is].second;
vector<int> ret1 = {is};
if (!visited[s]) visited[s] = typ;
while(!visited[cur]){
visited[cur] = typ;
ret1.push_back(adj[cur].begin()->second);
cur = adj[cur].begin()->first;
}
if (visited[cur]!=typ){ ///use same cycle
flag = 1;
vector<int> ret2;
while(visited[cur]!=typ){
visited[cur] = typ;
if (!cyc[adj[cur].begin()->second]){
assert(cur==s);
ret2.push_back(adj[cur].rbegin()->second);
cur = adj[cur].rbegin()->first;
continue;
}
ret2.push_back(adj[cur].begin()->second);
cur = adj[cur].begin()->first;
}
return {ret1, ret2};
}
int tmp = cur==s?is:adj[cur].begin()->second;
auto iter = find(ret1.begin(), ret1.end(), tmp);
vector<int> ret2(iter, ret1.end());
ret1.erase(iter, ret1.end());
for (auto &x:ret1) visited[E[x].first] = 0;
for (auto &x:ret2) {flip(x); cyc[x] = 1;}
return {ret1, ret2};
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
n = N, s = 1;
fill(on+1, on+n+1, 1);
for (int i=0;i<M;i++){
++U[i], ++V[i];
adj[U[i]].emplace(V[i], i);
INV[V[i]].emplace(U[i], i);
E[i] = {U[i], V[i]};
}
for (int i=1;i<=n;i++) if (adj[i].empty()) deg0.push_back(i);
while(true){
while(!deg0.empty()){
int x = deg0.back(); deg0.pop_back();
_erase(x);
}
if (!on[s]) return false;
if (adj[s].size()>1) break;
ansf.push_back(adj[s].begin()->second);
ansb.push_back(adj[s].begin()->second);
int nxt = adj[s].begin()->first;
_erase(s);
s = nxt;
}
for (int i=1;i<=n;i++) if (on[i]){
int sz = (i==s)?2:1;
while((int)adj[i].size()>sz) pop(i);
}
int i1 = adj[s].begin()->second, i2 = adj[s].rbegin()->second;
auto [p1, c1] = solve(i1, 1);
auto [p2, c2] = solve(i2, 2);
/*printf("flag = %d\n", flag);
for (auto &x:p1) printf("%d ", x);
printf("\n");
for (auto &x:c1) printf("%d ", x);
printf("\n");
for (auto &x:p2) printf("%d ", x);
printf("\n");
for (auto &x:c2) printf("%d ", x);
printf("\n");*/
if (flag) return ansf + p1 + c1 + rev(p1) + p2 + c2 + rev(p2) + rev(ansb);
return ansf + p1 + c1 + rev(p1) + p2 + c2 + rev(p2) + p1 + rev(c1) + rev(p1) + p2 + rev(c2) + rev(p2) + rev(ansb);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9668 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9600 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
128 ms |
33168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9684 KB |
Output is correct |
3 |
Correct |
6 ms |
9620 KB |
Output is correct |
4 |
Correct |
6 ms |
9708 KB |
Output is correct |
5 |
Correct |
5 ms |
9724 KB |
Output is correct |
6 |
Correct |
186 ms |
28408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
10196 KB |
Output is correct |
2 |
Correct |
5 ms |
9748 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
8 ms |
9940 KB |
Output is correct |
6 |
Correct |
7 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9812 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
7 ms |
9940 KB |
Output is correct |
11 |
Correct |
6 ms |
9684 KB |
Output is correct |
12 |
Correct |
6 ms |
9940 KB |
Output is correct |
13 |
Correct |
7 ms |
9684 KB |
Output is correct |
14 |
Correct |
5 ms |
9684 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
7 ms |
9684 KB |
Output is correct |
17 |
Correct |
105 ms |
21376 KB |
Output is correct |
18 |
Correct |
67 ms |
19120 KB |
Output is correct |
19 |
Correct |
5 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9660 KB |
Output is correct |
21 |
Correct |
8 ms |
9648 KB |
Output is correct |
22 |
Correct |
5 ms |
9684 KB |
Output is correct |
23 |
Correct |
170 ms |
28440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9684 KB |
Output is correct |
2 |
Correct |
8 ms |
10128 KB |
Output is correct |
3 |
Correct |
196 ms |
30800 KB |
Output is correct |
4 |
Correct |
186 ms |
30968 KB |
Output is correct |
5 |
Correct |
8 ms |
10068 KB |
Output is correct |
6 |
Correct |
7 ms |
10128 KB |
Output is correct |
7 |
Correct |
6 ms |
9604 KB |
Output is correct |
8 |
Correct |
7 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
7 ms |
10068 KB |
Output is correct |
11 |
Correct |
7 ms |
10068 KB |
Output is correct |
12 |
Correct |
9 ms |
10184 KB |
Output is correct |
13 |
Correct |
7 ms |
10196 KB |
Output is correct |
14 |
Correct |
10 ms |
10196 KB |
Output is correct |
15 |
Correct |
11 ms |
10324 KB |
Output is correct |
16 |
Correct |
7 ms |
9940 KB |
Output is correct |
17 |
Correct |
5 ms |
9684 KB |
Output is correct |
18 |
Correct |
7 ms |
10212 KB |
Output is correct |
19 |
Correct |
14 ms |
9940 KB |
Output is correct |
20 |
Correct |
209 ms |
33120 KB |
Output is correct |
21 |
Correct |
276 ms |
30828 KB |
Output is correct |
22 |
Correct |
7 ms |
9940 KB |
Output is correct |
23 |
Correct |
6 ms |
9812 KB |
Output is correct |
24 |
Correct |
8 ms |
9632 KB |
Output is correct |
25 |
Correct |
7 ms |
9940 KB |
Output is correct |
26 |
Correct |
7 ms |
9940 KB |
Output is correct |
27 |
Correct |
240 ms |
32388 KB |
Output is correct |
28 |
Correct |
230 ms |
32056 KB |
Output is correct |
29 |
Correct |
5 ms |
9684 KB |
Output is correct |
30 |
Correct |
222 ms |
33164 KB |
Output is correct |
31 |
Correct |
5 ms |
9684 KB |
Output is correct |
32 |
Correct |
222 ms |
30852 KB |
Output is correct |
33 |
Correct |
204 ms |
32024 KB |
Output is correct |
34 |
Correct |
89 ms |
21428 KB |
Output is correct |
35 |
Correct |
9 ms |
9832 KB |
Output is correct |
36 |
Correct |
187 ms |
28484 KB |
Output is correct |
37 |
Correct |
254 ms |
32028 KB |
Output is correct |
38 |
Correct |
7 ms |
9940 KB |
Output is correct |
39 |
Correct |
201 ms |
27704 KB |
Output is correct |
40 |
Correct |
9 ms |
10080 KB |
Output is correct |
41 |
Correct |
259 ms |
33180 KB |
Output is correct |
42 |
Correct |
253 ms |
32072 KB |
Output is correct |
43 |
Correct |
6 ms |
9684 KB |
Output is correct |
44 |
Correct |
7 ms |
10196 KB |
Output is correct |
45 |
Correct |
6 ms |
9940 KB |
Output is correct |
46 |
Correct |
63 ms |
19120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9668 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9600 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
128 ms |
33168 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
7 ms |
9684 KB |
Output is correct |
10 |
Correct |
6 ms |
9620 KB |
Output is correct |
11 |
Correct |
6 ms |
9708 KB |
Output is correct |
12 |
Correct |
5 ms |
9724 KB |
Output is correct |
13 |
Correct |
186 ms |
28408 KB |
Output is correct |
14 |
Correct |
9 ms |
10196 KB |
Output is correct |
15 |
Correct |
5 ms |
9748 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
5 ms |
9684 KB |
Output is correct |
18 |
Correct |
8 ms |
9940 KB |
Output is correct |
19 |
Correct |
7 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9812 KB |
Output is correct |
21 |
Correct |
5 ms |
9684 KB |
Output is correct |
22 |
Correct |
5 ms |
9684 KB |
Output is correct |
23 |
Correct |
7 ms |
9940 KB |
Output is correct |
24 |
Correct |
6 ms |
9684 KB |
Output is correct |
25 |
Correct |
6 ms |
9940 KB |
Output is correct |
26 |
Correct |
7 ms |
9684 KB |
Output is correct |
27 |
Correct |
5 ms |
9684 KB |
Output is correct |
28 |
Correct |
5 ms |
9684 KB |
Output is correct |
29 |
Correct |
7 ms |
9684 KB |
Output is correct |
30 |
Correct |
105 ms |
21376 KB |
Output is correct |
31 |
Correct |
67 ms |
19120 KB |
Output is correct |
32 |
Correct |
5 ms |
9684 KB |
Output is correct |
33 |
Correct |
5 ms |
9660 KB |
Output is correct |
34 |
Correct |
8 ms |
9648 KB |
Output is correct |
35 |
Correct |
5 ms |
9684 KB |
Output is correct |
36 |
Correct |
170 ms |
28440 KB |
Output is correct |
37 |
Correct |
6 ms |
9684 KB |
Output is correct |
38 |
Correct |
5 ms |
9684 KB |
Output is correct |
39 |
Correct |
6 ms |
9684 KB |
Output is correct |
40 |
Correct |
6 ms |
9812 KB |
Output is correct |
41 |
Correct |
113 ms |
20284 KB |
Output is correct |
42 |
Correct |
8 ms |
10300 KB |
Output is correct |
43 |
Correct |
132 ms |
21648 KB |
Output is correct |
44 |
Correct |
128 ms |
21656 KB |
Output is correct |
45 |
Correct |
120 ms |
21612 KB |
Output is correct |
46 |
Correct |
5 ms |
9684 KB |
Output is correct |
47 |
Correct |
5 ms |
9728 KB |
Output is correct |
48 |
Correct |
6 ms |
9684 KB |
Output is correct |
49 |
Correct |
6 ms |
9940 KB |
Output is correct |
50 |
Correct |
161 ms |
30248 KB |
Output is correct |
51 |
Correct |
289 ms |
33484 KB |
Output is correct |
52 |
Correct |
291 ms |
33580 KB |
Output is correct |
53 |
Correct |
323 ms |
34080 KB |
Output is correct |
54 |
Correct |
292 ms |
33584 KB |
Output is correct |
55 |
Correct |
265 ms |
33500 KB |
Output is correct |
56 |
Correct |
273 ms |
33700 KB |
Output is correct |
57 |
Correct |
213 ms |
32880 KB |
Output is correct |
58 |
Correct |
130 ms |
33604 KB |
Output is correct |
59 |
Correct |
228 ms |
33952 KB |
Output is correct |
60 |
Correct |
260 ms |
33952 KB |
Output is correct |
61 |
Correct |
232 ms |
33772 KB |
Output is correct |
62 |
Correct |
23 ms |
13780 KB |
Output is correct |
63 |
Correct |
174 ms |
32464 KB |
Output is correct |
64 |
Correct |
121 ms |
21964 KB |
Output is correct |
65 |
Correct |
5 ms |
9664 KB |
Output is correct |
66 |
Correct |
6 ms |
9812 KB |
Output is correct |
67 |
Correct |
210 ms |
34312 KB |
Output is correct |
68 |
Correct |
336 ms |
33268 KB |
Output is correct |
69 |
Correct |
108 ms |
22144 KB |
Output is correct |
70 |
Correct |
6 ms |
9940 KB |
Output is correct |
71 |
Correct |
175 ms |
27592 KB |
Output is correct |
72 |
Correct |
6 ms |
9684 KB |
Output is correct |
73 |
Correct |
252 ms |
33544 KB |
Output is correct |
74 |
Correct |
121 ms |
29324 KB |
Output is correct |
75 |
Correct |
14 ms |
10964 KB |
Output is correct |
76 |
Correct |
53 ms |
18616 KB |
Output is correct |
77 |
Correct |
86 ms |
21852 KB |
Output is correct |
78 |
Correct |
254 ms |
33952 KB |
Output is correct |
79 |
Correct |
5 ms |
9684 KB |
Output is correct |
80 |
Correct |
266 ms |
38536 KB |
Output is correct |
81 |
Correct |
6 ms |
10068 KB |
Output is correct |
82 |
Correct |
182 ms |
33172 KB |
Output is correct |
83 |
Correct |
6 ms |
9812 KB |
Output is correct |
84 |
Correct |
5 ms |
9684 KB |
Output is correct |
85 |
Correct |
62 ms |
20272 KB |
Output is correct |
86 |
Correct |
5 ms |
9940 KB |
Output is correct |
87 |
Correct |
8 ms |
10876 KB |
Output is correct |
88 |
Correct |
7 ms |
10384 KB |
Output is correct |
89 |
Correct |
258 ms |
33876 KB |
Output is correct |
90 |
Correct |
240 ms |
33796 KB |
Output is correct |
91 |
Correct |
279 ms |
37832 KB |
Output is correct |
92 |
Correct |
5 ms |
9684 KB |
Output is correct |