#include <bits/stdc++.h>
#include <variant>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
vector<int > construct_journey(
vector<list<pair<int, int>>> nodes, int fork,
list<pair<int, int>>c2, list<pair<int, int>>c1_fork_to_cycle_pairs, list<pair<int, int>>c1_cycle_pairs, bool two_cycles) {
vector<int> journey;
if (two_cycles) {
list<int> start_to_fork, c1_fork_to_cycle, c1_cycle, c2_fork_to_cycle, c2_cycle;
// component2
int begin_cycle_c2 = c2.back().first;
c2_cycle.push_front(c2.back().second);
c2.pop_back();
while (c2.back().first != begin_cycle_c2) {
c2_cycle.push_front(c2.back().second);
c2.pop_back();
}
while (c2.back().first != fork) {
c2_fork_to_cycle.push_front(c2.back().second);
c2.pop_back();
}
while (!c2.empty()) {
start_to_fork.push_front(c2.back().second);
c2.pop_back();
}
start_to_fork.pop_front();
// component1
for (auto& i : c1_fork_to_cycle_pairs) {
c1_fork_to_cycle.push_back(i.second);
}
for (auto& i : c1_cycle_pairs) {
c1_cycle.push_back(i.second);
}
journey.reserve(2 * start_to_fork.size() + 4 * c1_fork_to_cycle.size() + 2 * c1_cycle.size() + 4 * c2_fork_to_cycle.size() + 2 * c2_cycle.size());
copy(start_to_fork.cbegin(), start_to_fork.cend(), back_inserter(journey));
copy(c1_fork_to_cycle.cbegin(), c1_fork_to_cycle.cend(), back_inserter(journey));
copy(c1_cycle.cbegin(), c1_cycle.cend(), back_inserter(journey));
copy(c1_fork_to_cycle.crbegin(), c1_fork_to_cycle.crend(), back_inserter(journey));
copy(c2_fork_to_cycle.cbegin(), c2_fork_to_cycle.cend(), back_inserter(journey));
copy(c2_cycle.cbegin(), c2_cycle.cend(), back_inserter(journey));
copy(c2_fork_to_cycle.crbegin(), c2_fork_to_cycle.crend(), back_inserter(journey));
copy(c1_fork_to_cycle.cbegin(), c1_fork_to_cycle.cend(), back_inserter(journey));
copy(c1_cycle.crbegin(), c1_cycle.crend(), back_inserter(journey));
copy(c1_fork_to_cycle.crbegin(), c1_fork_to_cycle.crend(), back_inserter(journey));
copy(c2_fork_to_cycle.cbegin(), c2_fork_to_cycle.cend(), back_inserter(journey));
copy(c2_cycle.crbegin(), c2_cycle.crend(), back_inserter(journey));
copy(c2_fork_to_cycle.crbegin(), c2_fork_to_cycle.crend(), back_inserter(journey));
copy(start_to_fork.crbegin(), start_to_fork.crend(), back_inserter(journey));
}
else {
list<int> start_to_fork, fork_to_join1, fork_to_join2, cycle;
// component2
while (c2.front().first != fork) {
start_to_fork.push_back(c2.front().second);
c2.pop_front();
}
start_to_fork.push_back(c2.front().second);
start_to_fork.pop_front();
c2.pop_front();
for (auto& i : c2) {
fork_to_join2.push_back(i.second);
}
for (auto& i : c1_cycle_pairs) {
cycle.push_back(i.second);
}
int join = c2.back().first;
// component1
auto it = c1_fork_to_cycle_pairs.cbegin();
while (it != c1_fork_to_cycle_pairs.cend() && (*it).first != join) {
fork_to_join1.push_back((*it++).second);
}
// join before the cycle
if (it != c1_fork_to_cycle_pairs.cend()) {
fork_to_join1.push_back((*it++).second);
list<int> join_to_cycle;
while (it != c1_fork_to_cycle_pairs.cend()) {
join_to_cycle.push_back((*it++).second);
}
journey.reserve(2 * start_to_fork.size() + 2 * fork_to_join1.size() + 2 * fork_to_join2.size() + 4 * join_to_cycle.size() + 2 * cycle.size());
copy(start_to_fork.cbegin(), start_to_fork.cend(), back_inserter(journey));
copy(fork_to_join1.cbegin(), fork_to_join1.cend(), back_inserter(journey));
copy(join_to_cycle.cbegin(), join_to_cycle.cend(), back_inserter(journey));
copy(cycle.cbegin(), cycle.cend(), back_inserter(journey));
copy(join_to_cycle.crbegin(), join_to_cycle.crend(), back_inserter(journey));
copy(fork_to_join1.crbegin(), fork_to_join1.crend(), back_inserter(journey));
copy(fork_to_join2.cbegin(), fork_to_join2.cend(), back_inserter(journey));
copy(join_to_cycle.cbegin(), join_to_cycle.cend(), back_inserter(journey));
copy(cycle.crbegin(), cycle.crend(), back_inserter(journey));
copy(join_to_cycle.crbegin(), join_to_cycle.crend(), back_inserter(journey));
copy(fork_to_join2.crbegin(), fork_to_join2.crend(), back_inserter(journey));
copy(start_to_fork.crbegin(), start_to_fork.crend(), back_inserter(journey));
}
// join inside the cycle
else {
journey.reserve(2 * start_to_fork.size() + 2 * fork_to_join1.size() + 2 * fork_to_join2.size() + 2 * cycle.size());
copy(start_to_fork.cbegin(), start_to_fork.cend(), back_inserter(journey));
copy(fork_to_join1.cbegin(), fork_to_join1.cend(), back_inserter(journey));
copy(cycle.cbegin(), cycle.cend(), back_inserter(journey));
copy(fork_to_join1.crbegin(), fork_to_join1.crend(), back_inserter(journey));
copy(fork_to_join2.cbegin(), fork_to_join2.cend(), back_inserter(journey));
// rotate the cycle
while (c1_cycle_pairs.back().first != join) {
c1_cycle_pairs.push_front(c1_cycle_pairs.back());
c1_cycle_pairs.pop_back();
cycle.push_front(cycle.back());
cycle.pop_back();
}
copy(cycle.crbegin(), cycle.crend(), back_inserter(journey));
copy(fork_to_join2.crbegin(), fork_to_join2.crend(), back_inserter(journey));
copy(start_to_fork.crbegin(), start_to_fork.crend(), back_inserter(journey));
}
}
return journey;
}
list<pair<int, int>> construct_cycle(vector<list<pair<int, int>>> nodes, int begin_cycle, vector<bool> unavailable_nodes) {
vector<bool> visited(nodes.size(), false);
vector<pair<int, int>> predecessors(nodes.size());
queue<int> bfs_queue;
visited[begin_cycle] = true;
bfs_queue.push(begin_cycle);
while (!bfs_queue.empty()) {
int last_node = bfs_queue.front();
bfs_queue.pop();
for (auto& next_edge : nodes[last_node]) {
if (!visited[next_edge.first] && !unavailable_nodes[next_edge.first]) {
visited[next_edge.first] = true;
bfs_queue.push(next_edge.first);
predecessors[next_edge.first] = make_pair(last_node, next_edge.second);
}
else if (next_edge.first == begin_cycle) {
list<pair<int, int>> cycle;
cycle.push_front(make_pair(next_edge.first, next_edge.second));
while (last_node != begin_cycle) {
cycle.push_front(make_pair(last_node, predecessors[last_node].second));
last_node = predecessors[last_node].first;
}
return cycle;
}
}
}
return {};
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
// pair out_node, out_edge
vector<list<pair<int, int>>> nodes(N);
for (auto i = 0; i < U.size(); i++) {
nodes[U[i]].push_back(make_pair(V[i], i));
}
vector<bool>
visited(nodes.size(), false),
in_path(nodes.size(), false),
begin_cycle(nodes.size(), false),
goal(nodes.size(), false);
stack<list<pair<int, int>>::const_iterator> dfs_stack;
list<pair<int, int>> path;
list<pair<int, int>> c1_fork_to_cycle, c1_cycle;
bool seek_component2 = false;
int fork = -1;
visited[0] = true;
in_path[0] = true;
dfs_stack.push(nodes[0].cbegin());
path.push_back(make_pair(0, -1));
while (!dfs_stack.empty()) {
int top_node = path.back().first;
goal[top_node] = seek_component2;
// first popped cycle -> found the cycle of component1
if (!seek_component2 && begin_cycle[top_node]) {
seek_component2 = true;
c1_cycle = construct_cycle(nodes, top_node, in_path);
visited = vector<bool>(nodes.size(), false);
for (auto& i : c1_cycle) {
visited[i.first] = true;
goal[i.first] = true;
}
for (auto& i : path) {
visited[i.first] = true;
}
}
// top_node has more successors
if (dfs_stack.top() != nodes[path.back().first].cend()) {
auto& [successor_node, successor_edge] = *dfs_stack.top();
dfs_stack.top()++;
// set new fork
if (seek_component2 && fork == -1) {
fork = top_node;
}
if (!visited[successor_node]) {
visited[successor_node] = true;
in_path[successor_node] = true;
dfs_stack.push(nodes[successor_node].cbegin());
path.push_back(make_pair(successor_node, successor_edge));
}
// found a cycle in component1
else if (!seek_component2 && in_path[successor_node]) {
begin_cycle[successor_node] = true;
}
// found component2
else if (goal[successor_node]) {
path.push_back(make_pair(successor_node, successor_edge));
// cycle found
if (in_path[successor_node]) {
return construct_journey(nodes, fork, path, c1_fork_to_cycle, c1_cycle, true);
}
// path to component1 found
else {
return construct_journey(nodes, fork, path, c1_fork_to_cycle, c1_cycle, false);
}
}
}
// top_node has no more successors -> pop it off the stack
else {
goal[top_node] = false;
if (top_node == fork) {
fork = -1;
}
if (seek_component2 && fork == -1) {
goal[top_node] = true;
c1_fork_to_cycle.push_front(path.back());
}
in_path[top_node] = false;
dfs_stack.pop();
path.pop_back();
}
}
return false;
}
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:169:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for (auto i = 0; i < U.size(); i++) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
51 ms |
16836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
440 KB |
Output is correct |
6 |
Correct |
46 ms |
13904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
432 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
704 KB |
Output is correct |
6 |
Correct |
1 ms |
436 KB |
Output is correct |
7 |
Correct |
1 ms |
436 KB |
Output is correct |
8 |
Correct |
1 ms |
432 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
0 ms |
548 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
27 ms |
9024 KB |
Output is correct |
18 |
Correct |
22 ms |
7260 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
45 ms |
13908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
61 ms |
15784 KB |
Output is correct |
4 |
Correct |
55 ms |
15700 KB |
Output is correct |
5 |
Correct |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
392 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
2 ms |
752 KB |
Output is correct |
15 |
Correct |
2 ms |
856 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
37 ms |
10824 KB |
Output is correct |
21 |
Correct |
79 ms |
15760 KB |
Output is correct |
22 |
Correct |
1 ms |
612 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
704 KB |
Output is correct |
27 |
Correct |
55 ms |
16564 KB |
Output is correct |
28 |
Correct |
65 ms |
16832 KB |
Output is correct |
29 |
Correct |
0 ms |
344 KB |
Output is correct |
30 |
Correct |
39 ms |
11344 KB |
Output is correct |
31 |
Correct |
0 ms |
344 KB |
Output is correct |
32 |
Correct |
63 ms |
15956 KB |
Output is correct |
33 |
Correct |
60 ms |
16224 KB |
Output is correct |
34 |
Correct |
27 ms |
9132 KB |
Output is correct |
35 |
Correct |
1 ms |
600 KB |
Output is correct |
36 |
Correct |
44 ms |
14064 KB |
Output is correct |
37 |
Correct |
62 ms |
16720 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
29 ms |
8804 KB |
Output is correct |
40 |
Correct |
1 ms |
600 KB |
Output is correct |
41 |
Correct |
38 ms |
11344 KB |
Output is correct |
42 |
Correct |
61 ms |
16804 KB |
Output is correct |
43 |
Correct |
0 ms |
344 KB |
Output is correct |
44 |
Correct |
1 ms |
604 KB |
Output is correct |
45 |
Correct |
2 ms |
604 KB |
Output is correct |
46 |
Correct |
22 ms |
7220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
51 ms |
16836 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
440 KB |
Output is correct |
13 |
Correct |
46 ms |
13904 KB |
Output is correct |
14 |
Correct |
1 ms |
600 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
432 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
704 KB |
Output is correct |
19 |
Correct |
1 ms |
436 KB |
Output is correct |
20 |
Correct |
1 ms |
436 KB |
Output is correct |
21 |
Correct |
1 ms |
432 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
604 KB |
Output is correct |
24 |
Correct |
0 ms |
548 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
27 ms |
9024 KB |
Output is correct |
31 |
Correct |
22 ms |
7260 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
344 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
45 ms |
13908 KB |
Output is correct |
37 |
Correct |
0 ms |
344 KB |
Output is correct |
38 |
Correct |
0 ms |
600 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
344 KB |
Output is correct |
41 |
Correct |
22 ms |
7784 KB |
Output is correct |
42 |
Correct |
2 ms |
860 KB |
Output is correct |
43 |
Correct |
30 ms |
12344 KB |
Output is correct |
44 |
Correct |
33 ms |
12376 KB |
Output is correct |
45 |
Correct |
37 ms |
12376 KB |
Output is correct |
46 |
Correct |
0 ms |
348 KB |
Output is correct |
47 |
Correct |
0 ms |
348 KB |
Output is correct |
48 |
Correct |
1 ms |
348 KB |
Output is correct |
49 |
Correct |
1 ms |
604 KB |
Output is correct |
50 |
Correct |
78 ms |
23580 KB |
Output is correct |
51 |
Correct |
51 ms |
16464 KB |
Output is correct |
52 |
Correct |
81 ms |
23492 KB |
Output is correct |
53 |
Correct |
80 ms |
23356 KB |
Output is correct |
54 |
Correct |
62 ms |
24320 KB |
Output is correct |
55 |
Correct |
75 ms |
24268 KB |
Output is correct |
56 |
Correct |
112 ms |
24144 KB |
Output is correct |
57 |
Correct |
57 ms |
21532 KB |
Output is correct |
58 |
Correct |
74 ms |
21656 KB |
Output is correct |
59 |
Correct |
70 ms |
14420 KB |
Output is correct |
60 |
Correct |
67 ms |
23896 KB |
Output is correct |
61 |
Correct |
44 ms |
14656 KB |
Output is correct |
62 |
Correct |
7 ms |
3164 KB |
Output is correct |
63 |
Correct |
42 ms |
13924 KB |
Output is correct |
64 |
Correct |
30 ms |
9044 KB |
Output is correct |
65 |
Correct |
0 ms |
344 KB |
Output is correct |
66 |
Correct |
1 ms |
348 KB |
Output is correct |
67 |
Correct |
88 ms |
24672 KB |
Output is correct |
68 |
Correct |
50 ms |
11344 KB |
Output is correct |
69 |
Correct |
27 ms |
9808 KB |
Output is correct |
70 |
Correct |
1 ms |
604 KB |
Output is correct |
71 |
Correct |
40 ms |
10332 KB |
Output is correct |
72 |
Correct |
0 ms |
344 KB |
Output is correct |
73 |
Correct |
63 ms |
13648 KB |
Output is correct |
74 |
Correct |
74 ms |
24668 KB |
Output is correct |
75 |
Correct |
3 ms |
1372 KB |
Output is correct |
76 |
Correct |
33 ms |
11416 KB |
Output is correct |
77 |
Correct |
43 ms |
18004 KB |
Output is correct |
78 |
Correct |
66 ms |
23888 KB |
Output is correct |
79 |
Correct |
0 ms |
348 KB |
Output is correct |
80 |
Correct |
108 ms |
28556 KB |
Output is correct |
81 |
Correct |
1 ms |
604 KB |
Output is correct |
82 |
Correct |
37 ms |
10572 KB |
Output is correct |
83 |
Correct |
1 ms |
348 KB |
Output is correct |
84 |
Correct |
0 ms |
348 KB |
Output is correct |
85 |
Correct |
33 ms |
10592 KB |
Output is correct |
86 |
Correct |
1 ms |
600 KB |
Output is correct |
87 |
Correct |
2 ms |
2396 KB |
Output is correct |
88 |
Correct |
2 ms |
1112 KB |
Output is correct |
89 |
Correct |
68 ms |
23884 KB |
Output is correct |
90 |
Correct |
52 ms |
14420 KB |
Output is correct |
91 |
Correct |
108 ms |
28140 KB |
Output is correct |
92 |
Correct |
0 ms |
344 KB |
Output is correct |