#include "islands.h"
#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
int s = 0;
vector<bool> e(N, true);
vector<int>ans0;
{
vector<int> C(N, 0);
vector<int>b[N];
vector<int>ff[N];
for (int i = 0; i < M; i++)
{
C[U[i]]++;
b[V[i]].push_back(U[i]);
ff[U[i]].push_back(i);
}
stack<int>Q;
for (int i = 0; i < N; i++)
if (C[i] == 0)
Q.push(i);
while (e[s])
{
if (C[s] == 1)
{
int s_ = -1;
for (int ee : ff[s])
{
if (e[V[ee]])
{
ans0.push_back(ee);
s_ = V[ee];
}
}
for (int t : b[s])
{
if (e[t])
{
C[t]--;
if (C[t] == 0)
Q.push(t);
}
}
e[s] = false;
s = s_;
continue;
}
if (Q.empty())
break;
int a = Q.top();
Q.pop();
if (!e[a])
continue;
e[a] = false;
for (int t : b[a])
{
if (e[t])
{
C[t]--;
if (C[t] == 0)
Q.push(t);
}
}
}
if (!e[s])
return false;
}
vector<int>adj[N];
vector<int>adj_[N];
for (int i = 0; i < M; i++)
if (e[U[i]] && e[V[i]])
adj[U[i]].push_back(i);
for (int i = 0; i < N; i++)
if (i != s)
while (adj[i].size() > 1)
adj[i].pop_back();
while (adj[s].size() > 2)
adj[s].pop_back();
for (int i = 0; i < N; i++)
for (int e : adj[i])
{
adj_[V[e]].push_back(e);
}
vector<int>ret = ans0;
int ss = 0;
vector<bool> state(M, false);
bool fnd = false;
function<void(int, int)> dfs = [&](int i, int e)->void
{
if (i == s && e != -1 && ss == 0)
{
fnd = true;
return;
}
for (int ee : adj[i])
{
int j = V[ee];
if (e == ee || state[ee] == true)
continue;
state[ee] = true;
ret.push_back(ee);
ss++;
dfs(j, ee);
ss--;
if (fnd)
return;
ret.pop_back();
state[ee] = false;
}
for (int ee : adj_[i])
{
int j = U[ee];
if (e == ee || state[ee] == false)
continue;
state[ee] = false;
ss--;
ret.push_back(ee);
dfs(j, ee);
if (fnd)
return;
ss++;
ret.pop_back();
state[ee] = true;
}
};
dfs(s, -1);
reverse(ans0.begin(), ans0.end());
for (int i : ans0)
ret.push_back(i);
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 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 |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
43 ms |
5116 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 |
1 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 |
35 ms |
4612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 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 |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
25 ms |
3012 KB |
Output is correct |
18 |
Correct |
18 ms |
2736 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
34 ms |
4512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
40 ms |
5040 KB |
Output is correct |
4 |
Correct |
37 ms |
5296 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 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 |
2 ms |
852 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
596 KB |
Output is correct |
14 |
Correct |
2 ms |
596 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
252 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
35 ms |
5848 KB |
Output is correct |
21 |
Correct |
36 ms |
5420 KB |
Output is correct |
22 |
Correct |
1 ms |
436 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
2 ms |
596 KB |
Output is correct |
27 |
Correct |
40 ms |
5500 KB |
Output is correct |
28 |
Correct |
39 ms |
5580 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
44 ms |
6220 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
40 ms |
5552 KB |
Output is correct |
33 |
Correct |
37 ms |
5368 KB |
Output is correct |
34 |
Correct |
21 ms |
3072 KB |
Output is correct |
35 |
Correct |
1 ms |
468 KB |
Output is correct |
36 |
Correct |
33 ms |
4760 KB |
Output is correct |
37 |
Correct |
43 ms |
5964 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
31 ms |
4836 KB |
Output is correct |
40 |
Correct |
1 ms |
468 KB |
Output is correct |
41 |
Correct |
43 ms |
6220 KB |
Output is correct |
42 |
Correct |
38 ms |
5628 KB |
Output is correct |
43 |
Correct |
0 ms |
212 KB |
Output is correct |
44 |
Correct |
2 ms |
468 KB |
Output is correct |
45 |
Correct |
2 ms |
724 KB |
Output is correct |
46 |
Correct |
17 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 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 |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
43 ms |
5116 KB |
Output is correct |
8 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
35 ms |
4612 KB |
Output is correct |
14 |
Correct |
2 ms |
468 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 |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
2 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
25 ms |
3012 KB |
Output is correct |
31 |
Correct |
18 ms |
2736 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
34 ms |
4512 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
17 ms |
2672 KB |
Output is correct |
42 |
Correct |
2 ms |
468 KB |
Output is correct |
43 |
Correct |
54 ms |
7736 KB |
Output is correct |
44 |
Correct |
36 ms |
7612 KB |
Output is correct |
45 |
Correct |
39 ms |
7608 KB |
Output is correct |
46 |
Correct |
0 ms |
212 KB |
Output is correct |
47 |
Correct |
0 ms |
212 KB |
Output is correct |
48 |
Correct |
0 ms |
212 KB |
Output is correct |
49 |
Correct |
1 ms |
596 KB |
Output is correct |
50 |
Correct |
204 ms |
37484 KB |
Output is correct |
51 |
Correct |
92 ms |
15120 KB |
Output is correct |
52 |
Correct |
113 ms |
15160 KB |
Output is correct |
53 |
Correct |
96 ms |
15168 KB |
Output is correct |
54 |
Correct |
113 ms |
15140 KB |
Output is correct |
55 |
Correct |
113 ms |
15108 KB |
Output is correct |
56 |
Correct |
97 ms |
15168 KB |
Output is correct |
57 |
Correct |
76 ms |
11420 KB |
Output is correct |
58 |
Correct |
225 ms |
44604 KB |
Output is correct |
59 |
Correct |
108 ms |
14276 KB |
Output is correct |
60 |
Correct |
101 ms |
13592 KB |
Output is correct |
61 |
Correct |
118 ms |
13688 KB |
Output is correct |
62 |
Correct |
18 ms |
4564 KB |
Output is correct |
63 |
Correct |
118 ms |
13776 KB |
Output is correct |
64 |
Correct |
24 ms |
3520 KB |
Output is correct |
65 |
Correct |
0 ms |
212 KB |
Output is correct |
66 |
Correct |
1 ms |
340 KB |
Output is correct |
67 |
Correct |
136 ms |
14172 KB |
Output is correct |
68 |
Correct |
43 ms |
6224 KB |
Output is correct |
69 |
Correct |
66 ms |
11292 KB |
Output is correct |
70 |
Correct |
2 ms |
596 KB |
Output is correct |
71 |
Correct |
53 ms |
8592 KB |
Output is correct |
72 |
Correct |
0 ms |
212 KB |
Output is correct |
73 |
Correct |
86 ms |
11584 KB |
Output is correct |
74 |
Correct |
185 ms |
38800 KB |
Output is correct |
75 |
Correct |
3 ms |
852 KB |
Output is correct |
76 |
Correct |
52 ms |
15764 KB |
Output is correct |
77 |
Correct |
67 ms |
13836 KB |
Output is correct |
78 |
Correct |
91 ms |
13696 KB |
Output is correct |
79 |
Correct |
1 ms |
212 KB |
Output is correct |
80 |
Correct |
170 ms |
29452 KB |
Output is correct |
81 |
Correct |
1 ms |
724 KB |
Output is correct |
82 |
Correct |
34 ms |
5420 KB |
Output is correct |
83 |
Correct |
1 ms |
340 KB |
Output is correct |
84 |
Correct |
0 ms |
212 KB |
Output is correct |
85 |
Correct |
56 ms |
18248 KB |
Output is correct |
86 |
Correct |
1 ms |
468 KB |
Output is correct |
87 |
Correct |
4 ms |
4692 KB |
Output is correct |
88 |
Correct |
2 ms |
596 KB |
Output is correct |
89 |
Correct |
89 ms |
13516 KB |
Output is correct |
90 |
Correct |
100 ms |
13644 KB |
Output is correct |
91 |
Correct |
169 ms |
25412 KB |
Output is correct |
92 |
Correct |
0 ms |
212 KB |
Output is correct |