#include <bits/stdc++.h>
using namespace std;
constexpr int N_MAX = 100000;
set<pair<int, int>> g[N_MAX], rg[N_MAX];
bitset<N_MAX> visited, in_dfs;
void delete_node(int u)
{
vector<int> to_delete;
for (auto const &[v, i] : g[u])
rg[v].erase(make_pair(u, i));
for (auto const &[v, i] : rg[u])
{
g[v].erase(make_pair(u, i));
if (g[v].empty())
to_delete.push_back(v);
}
g[u].clear();
rg[u].clear();
for (auto const &v : to_delete)
delete_node(v);
}
int find_cycle(int u, vector<int> &cycle, vector<int> &path_to_cycle)
{
if (in_dfs[u])
return u;
if (visited[u])
return -1;
visited[u] = 1;
in_dfs[u] = 1;
for (auto const &[v, i] : g[u])
{
int x = find_cycle(v, cycle, path_to_cycle);
if (x != -1)
{
cycle.push_back(i);
in_dfs[u] = 0;
return u == x ? -1 : x;
}
else if (!cycle.empty())
{
path_to_cycle.push_back(i);
in_dfs[u] = 0;
return -1;
}
}
in_dfs[u] = 0;
return -1;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
for (int i = 0; i < M; ++i)
g[U[i]].emplace(V[i], i), rg[V[i]].emplace(U[i], i);
for (int i = 0; i < N; ++i)
if (g[i].empty())
delete_node(i);
int x = 0;
vector<int> line;
while (g[x].size() == 1)
{
int y = g[x].begin()->first;
line.push_back(g[x].begin()->second);
delete_node(x);
x = y;
}
if (g[x].empty())
return false;
vector<int> cycle_a, path_to_cycle_a, cycle_b, path_to_cycle_b;
find_cycle(x, cycle_a, path_to_cycle_a);
visited.reset();
g[x].erase(g[x].begin());
find_cycle(x, cycle_b, path_to_cycle_b);
assert(!cycle_a.empty() && !cycle_b.empty());
reverse(cycle_a.begin(), cycle_a.end());
reverse(cycle_b.begin(), cycle_b.end());
reverse(path_to_cycle_a.begin(), path_to_cycle_a.end());
reverse(path_to_cycle_b.begin(), path_to_cycle_b.end());
vector<int> cycle_a_ind(M, -1);
for (int i = 0; i < cycle_a.size(); ++i)
cycle_a_ind[cycle_a[i]] = i;
int common_a = -1, common_b = -1;
for (int i = 0; i < cycle_b.size(); ++i)
if (cycle_a_ind[cycle_b[i]] != -1)
{
common_a = cycle_a_ind[cycle_b[i]];
common_b = i;
break;
}
vector<int> tour = line;
if (common_a == -1)
{
tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
tour.insert(tour.end(), cycle_a.begin(), cycle_a.end());
tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
reverse(tour.end() - path_to_cycle_a.size(), tour.end());
tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
tour.insert(tour.end(), cycle_b.begin(), cycle_b.end());
tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
reverse(tour.end() - path_to_cycle_b.size(), tour.end());
tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
tour.insert(tour.end(), cycle_a.begin(), cycle_a.end());
reverse(tour.end() - cycle_a.size(), tour.end());
tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
reverse(tour.end() - path_to_cycle_a.size(), tour.end());
tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
tour.insert(tour.end(), cycle_b.begin(), cycle_b.end());
reverse(tour.end() - cycle_b.size(), tour.end());
tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
reverse(tour.end() - path_to_cycle_b.size(), tour.end());
}
else
{
tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
tour.insert(tour.end(), cycle_a.begin(), cycle_a.end());
tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
reverse(tour.end() - path_to_cycle_a.size(), tour.end());
tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
tour.insert(tour.end(), cycle_b.begin(), cycle_b.begin() + common_b);
rotate(cycle_a.begin(), cycle_a.begin() + common_a, cycle_a.end());
tour.insert(tour.end(), cycle_a.begin(), cycle_a.end());
reverse(tour.end() - cycle_a.size(), tour.end());
tour.insert(tour.end(), cycle_b.begin(), cycle_b.begin() + common_b);
reverse(tour.end() - common_b, tour.end());
tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
reverse(tour.end() - path_to_cycle_b.size(), tour.end());
}
tour.insert(tour.end(), line.begin(), line.end());
reverse(tour.end() - line.size(), tour.end());
return tour;
}
Compilation message
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i = 0; i < cycle_a.size(); ++i)
| ~~^~~~~~~~~~~~~~~~
islands.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int i = 0; i < cycle_b.size(); ++i)
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9696 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
87 ms |
33080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9700 KB |
Output is correct |
3 |
Correct |
4 ms |
9680 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
124 ms |
28536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10192 KB |
Output is correct |
2 |
Correct |
4 ms |
9700 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9696 KB |
Output is correct |
5 |
Correct |
5 ms |
9940 KB |
Output is correct |
6 |
Correct |
4 ms |
9700 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 |
9636 KB |
Output is correct |
10 |
Correct |
5 ms |
9940 KB |
Output is correct |
11 |
Correct |
4 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9940 KB |
Output is correct |
13 |
Correct |
4 ms |
9684 KB |
Output is correct |
14 |
Correct |
4 ms |
9684 KB |
Output is correct |
15 |
Correct |
4 ms |
9684 KB |
Output is correct |
16 |
Correct |
4 ms |
9684 KB |
Output is correct |
17 |
Correct |
64 ms |
21632 KB |
Output is correct |
18 |
Correct |
44 ms |
19300 KB |
Output is correct |
19 |
Correct |
4 ms |
9604 KB |
Output is correct |
20 |
Correct |
4 ms |
9696 KB |
Output is correct |
21 |
Correct |
4 ms |
9704 KB |
Output is correct |
22 |
Correct |
4 ms |
9684 KB |
Output is correct |
23 |
Correct |
153 ms |
28424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9700 KB |
Output is correct |
2 |
Correct |
6 ms |
10068 KB |
Output is correct |
3 |
Correct |
130 ms |
30844 KB |
Output is correct |
4 |
Correct |
142 ms |
30880 KB |
Output is correct |
5 |
Correct |
5 ms |
10068 KB |
Output is correct |
6 |
Correct |
6 ms |
10228 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
4 ms |
9696 KB |
Output is correct |
9 |
Correct |
5 ms |
9700 KB |
Output is correct |
10 |
Correct |
5 ms |
10068 KB |
Output is correct |
11 |
Correct |
6 ms |
10220 KB |
Output is correct |
12 |
Correct |
6 ms |
10224 KB |
Output is correct |
13 |
Correct |
6 ms |
10228 KB |
Output is correct |
14 |
Correct |
6 ms |
10092 KB |
Output is correct |
15 |
Correct |
6 ms |
10348 KB |
Output is correct |
16 |
Correct |
5 ms |
9940 KB |
Output is correct |
17 |
Correct |
4 ms |
9696 KB |
Output is correct |
18 |
Correct |
6 ms |
10068 KB |
Output is correct |
19 |
Correct |
5 ms |
9940 KB |
Output is correct |
20 |
Correct |
156 ms |
32236 KB |
Output is correct |
21 |
Correct |
145 ms |
30844 KB |
Output is correct |
22 |
Correct |
5 ms |
10092 KB |
Output is correct |
23 |
Correct |
6 ms |
9812 KB |
Output is correct |
24 |
Correct |
4 ms |
9700 KB |
Output is correct |
25 |
Correct |
5 ms |
9940 KB |
Output is correct |
26 |
Correct |
5 ms |
10068 KB |
Output is correct |
27 |
Correct |
138 ms |
32024 KB |
Output is correct |
28 |
Correct |
135 ms |
32008 KB |
Output is correct |
29 |
Correct |
4 ms |
9684 KB |
Output is correct |
30 |
Correct |
155 ms |
32344 KB |
Output is correct |
31 |
Correct |
4 ms |
9656 KB |
Output is correct |
32 |
Correct |
155 ms |
30800 KB |
Output is correct |
33 |
Correct |
142 ms |
31992 KB |
Output is correct |
34 |
Correct |
54 ms |
21712 KB |
Output is correct |
35 |
Correct |
5 ms |
9812 KB |
Output is correct |
36 |
Correct |
121 ms |
28512 KB |
Output is correct |
37 |
Correct |
154 ms |
32032 KB |
Output is correct |
38 |
Correct |
5 ms |
9812 KB |
Output is correct |
39 |
Correct |
112 ms |
27308 KB |
Output is correct |
40 |
Correct |
5 ms |
9940 KB |
Output is correct |
41 |
Correct |
152 ms |
32384 KB |
Output is correct |
42 |
Correct |
150 ms |
31988 KB |
Output is correct |
43 |
Correct |
5 ms |
9684 KB |
Output is correct |
44 |
Correct |
6 ms |
10068 KB |
Output is correct |
45 |
Correct |
5 ms |
10068 KB |
Output is correct |
46 |
Correct |
38 ms |
19392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9696 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
87 ms |
33080 KB |
Output is correct |
8 |
Correct |
4 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9700 KB |
Output is correct |
10 |
Correct |
4 ms |
9680 KB |
Output is correct |
11 |
Correct |
4 ms |
9684 KB |
Output is correct |
12 |
Correct |
4 ms |
9684 KB |
Output is correct |
13 |
Correct |
124 ms |
28536 KB |
Output is correct |
14 |
Correct |
6 ms |
10192 KB |
Output is correct |
15 |
Correct |
4 ms |
9700 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
4 ms |
9696 KB |
Output is correct |
18 |
Correct |
5 ms |
9940 KB |
Output is correct |
19 |
Correct |
4 ms |
9700 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 |
9636 KB |
Output is correct |
23 |
Correct |
5 ms |
9940 KB |
Output is correct |
24 |
Correct |
4 ms |
9684 KB |
Output is correct |
25 |
Correct |
5 ms |
9940 KB |
Output is correct |
26 |
Correct |
4 ms |
9684 KB |
Output is correct |
27 |
Correct |
4 ms |
9684 KB |
Output is correct |
28 |
Correct |
4 ms |
9684 KB |
Output is correct |
29 |
Correct |
4 ms |
9684 KB |
Output is correct |
30 |
Correct |
64 ms |
21632 KB |
Output is correct |
31 |
Correct |
44 ms |
19300 KB |
Output is correct |
32 |
Correct |
4 ms |
9604 KB |
Output is correct |
33 |
Correct |
4 ms |
9696 KB |
Output is correct |
34 |
Correct |
4 ms |
9704 KB |
Output is correct |
35 |
Correct |
4 ms |
9684 KB |
Output is correct |
36 |
Correct |
153 ms |
28424 KB |
Output is correct |
37 |
Correct |
5 ms |
9684 KB |
Output is correct |
38 |
Correct |
4 ms |
9696 KB |
Output is correct |
39 |
Correct |
4 ms |
9700 KB |
Output is correct |
40 |
Correct |
5 ms |
9812 KB |
Output is correct |
41 |
Correct |
67 ms |
19988 KB |
Output is correct |
42 |
Correct |
7 ms |
10196 KB |
Output is correct |
43 |
Correct |
108 ms |
29132 KB |
Output is correct |
44 |
Correct |
87 ms |
29196 KB |
Output is correct |
45 |
Correct |
104 ms |
29148 KB |
Output is correct |
46 |
Correct |
4 ms |
9684 KB |
Output is correct |
47 |
Correct |
4 ms |
9696 KB |
Output is correct |
48 |
Correct |
4 ms |
9684 KB |
Output is correct |
49 |
Correct |
5 ms |
9828 KB |
Output is correct |
50 |
Correct |
113 ms |
28064 KB |
Output is correct |
51 |
Correct |
234 ms |
48024 KB |
Output is correct |
52 |
Correct |
273 ms |
47972 KB |
Output is correct |
53 |
Correct |
236 ms |
48784 KB |
Output is correct |
54 |
Correct |
241 ms |
48072 KB |
Output is correct |
55 |
Correct |
284 ms |
48060 KB |
Output is correct |
56 |
Correct |
249 ms |
48044 KB |
Output is correct |
57 |
Correct |
200 ms |
32736 KB |
Output is correct |
58 |
Correct |
94 ms |
27192 KB |
Output is correct |
59 |
Correct |
228 ms |
32320 KB |
Output is correct |
60 |
Correct |
211 ms |
33176 KB |
Output is correct |
61 |
Correct |
240 ms |
32332 KB |
Output is correct |
62 |
Correct |
19 ms |
13500 KB |
Output is correct |
63 |
Correct |
133 ms |
31300 KB |
Output is correct |
64 |
Correct |
77 ms |
21736 KB |
Output is correct |
65 |
Correct |
4 ms |
9608 KB |
Output is correct |
66 |
Correct |
5 ms |
9832 KB |
Output is correct |
67 |
Correct |
140 ms |
33252 KB |
Output is correct |
68 |
Correct |
233 ms |
32380 KB |
Output is correct |
69 |
Correct |
86 ms |
25296 KB |
Output is correct |
70 |
Correct |
5 ms |
9940 KB |
Output is correct |
71 |
Correct |
127 ms |
26868 KB |
Output is correct |
72 |
Correct |
4 ms |
9684 KB |
Output is correct |
73 |
Correct |
184 ms |
32392 KB |
Output is correct |
74 |
Correct |
98 ms |
30160 KB |
Output is correct |
75 |
Correct |
9 ms |
10964 KB |
Output is correct |
76 |
Correct |
38 ms |
19404 KB |
Output is correct |
77 |
Correct |
105 ms |
36608 KB |
Output is correct |
78 |
Correct |
223 ms |
33068 KB |
Output is correct |
79 |
Correct |
4 ms |
9700 KB |
Output is correct |
80 |
Correct |
202 ms |
38416 KB |
Output is correct |
81 |
Correct |
5 ms |
9812 KB |
Output is correct |
82 |
Correct |
153 ms |
32376 KB |
Output is correct |
83 |
Correct |
5 ms |
9812 KB |
Output is correct |
84 |
Correct |
5 ms |
9620 KB |
Output is correct |
85 |
Correct |
35 ms |
18700 KB |
Output is correct |
86 |
Correct |
5 ms |
9964 KB |
Output is correct |
87 |
Correct |
6 ms |
9940 KB |
Output is correct |
88 |
Correct |
8 ms |
10252 KB |
Output is correct |
89 |
Correct |
194 ms |
33028 KB |
Output is correct |
90 |
Correct |
246 ms |
32432 KB |
Output is correct |
91 |
Correct |
207 ms |
37524 KB |
Output is correct |
92 |
Correct |
4 ms |
9684 KB |
Output is correct |