// model_solution/solution.cpp
#include "islands.h"
#include <bits/stdc++.h>
#define edge std::pair<int,int>
int mode[111000];
std::vector<std::set<edge>> back_path(222000);
std::vector<std::set<edge>> path(222000);
std::queue<int> remove_q;
bool must_flip = false;
int path_1_loop, path_2_loop;
void put_path(std::vector<int> &sol, std::vector<int> &mirror_sol, std::vector<std::pair<int, int>> &path_1, int loop_id) {
bool start = false;
for (int i = 1; i < (int) path_1.size(); i++) {
int u = path_1[i - 1].first;
int v = path_1[i].first;
if ((!start && u == loop_id) || (start && v == loop_id)) {
start = 1;
mirror_sol.push_back(1);
}
else
mirror_sol.push_back(0);
if (path_1[i].second == 1)
sol.push_back(path[u].begin()->first);
else
sol.push_back(path[v].begin()->first);
}
}
// remove a node X
void remove_node(int X) {
// remove node 'curr', and all paths from/to them
for (auto e: back_path[X]) {
auto e_id = e.first;
auto v = e.second;
path[v].erase({e_id, X});
if ((int) path[v].size() == 0) remove_q.push(v);
}
for (auto e: path[X]) {
auto e_id = e.first;
auto v = e.second;
back_path[v].erase({e_id, X});
}
}
// chain-remove all 0 outdegrees
void clear_unused_nodes() {
while (remove_q.size()) {
int curr = remove_q.front();
remove_q.pop();
remove_node(curr);
}
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
// construct the graph
for (int i = 0; i < M; i++) {
path[U[i]].insert({i, V[i]});
back_path[V[i]].insert({i, U[i]});
}
for (int i = 0; i < N; i++)
if ((int) path[i].size() == 0) remove_q.push(i);
int START = 0;
std::vector<int> backtrack;
std::vector<int> init_sol;
std::vector<int> back_sol;
while (true) {
clear_unused_nodes();
// if START is removed, then no solution
if ((int) path[START].size() == 0) return false;
// if START outdeg is 1, move forward and start from there.
if ((int) path[START].size() == 1) {
backtrack.push_back(START);
auto prev_start = START;
init_sol.push_back(path[START].begin()->first);
back_sol.push_back(path[START].begin()->first);
START = path[START].begin()->second;
remove_node(prev_start);
continue;
}
// now, we start at START, which has >= 2 outdeg.
// find a solution.
// step 1: find a loop
bool seen[111000];
memset(seen, 0, sizeof(seen));
// path notation: second denotes direction
std::vector<std::pair<int, int>> path_1;
std::vector<int> first_loop;
int curr = START;
while (true) {
path_1.push_back({curr, 1});
mode[curr] = 1;
// loop found
if (seen[curr]) {
path_1_loop = curr;
int X = path_1.size();
bool reverse_mode = false;
for (int i = X - 1; i >= 0; i--) {
if (reverse_mode) {
path_1.push_back({path_1[i].first, 0});
}
else {
// the loop
first_loop.push_back(path_1[i].first);
mode[path_1[i].first] = 2;
}
if (i != X - 1 && path_1[i].first == curr) reverse_mode = true;
}
break;
}
seen[curr] = 1;
int next = path[curr].begin()->second; /// guaranteed exists
curr = next;
}
// step 2: find another loop
// path notation: second denotes direction
std::vector<std::pair<int, int>> path_2;
curr = path[START].rbegin()->second;
while (true) {
path_2_loop = curr;
path_2.push_back({curr, 1});
if (seen[curr]) {
// 3 cases:
// 1st cases, found a straight path from path_1.
if (mode[curr] == 1) {
int curr2 = path[curr].begin()->second;
while (mode[curr2] == 1) {
path_2.push_back({curr2, 1});
curr2 = path[curr2].begin()->second;
}
//backloop
path_2.push_back({first_loop[0], 1});
for (int i = 1; i < (int) first_loop.size(); i++) {
path_2.push_back({first_loop[i], 0});
}
// set for trackback
curr = first_loop[0];
}
else if (mode[curr] == 2) {
// go back reverse circle
// find the starting point
int st = 0;
for (int i = 0; i < (int) first_loop.size(); i++) {
if (first_loop[i] == curr) {
st = i + 1;
break;
}
}
// from st to end
for (int i = st; i < (int) first_loop.size(); i++) {
path_2.push_back({first_loop[i], 0});
}
// from begin to st
for (int i = 1; i < st; i++) {
path_2.push_back({first_loop[i], 0});
}
} else if (mode[curr] == 3) {
must_flip = true;
}
int X = path_2.size();
bool reverse_mode = false;
for (int i = X - 1; i >= 0; i--) {
if (reverse_mode) {
path_2.push_back({path_2[i].first, 0});
}
if (i != X - 1 && path_2[i].first == curr) reverse_mode = true;
}
break;
}
mode[curr] = 3;
seen[curr] = 1;
curr = path[curr].begin()->second;
}
// has a solution
// convert paths to edges
std::vector<int> sol;
std::vector<int> mirror_sol;
put_path(sol, mirror_sol, path_1, path_1_loop);
mirror_sol.push_back(0);
sol.push_back(path[START].rbegin()->first);
put_path(sol, mirror_sol, path_2, path_2_loop);
mirror_sol.push_back(0);
sol.push_back(path[START].rbegin()->first);
if (must_flip) {
int X = sol.size();
std::stack<int> stack_path;
bool stack_fill_mode = 0;
for (int i = 0; i < X; i++) {
while (!stack_fill_mode && stack_path.size()) {
int tmp = stack_path.top();
stack_path.pop();
sol.push_back(tmp);
}
if (mirror_sol[i] == 1) {
stack_fill_mode ^= 1;
}
if (stack_fill_mode)
stack_path.push(sol[i]);
else
sol.push_back(sol[i]);
}
}
for (auto x: sol){
init_sol.push_back(x);
}
std::reverse(back_sol.begin(), back_sol.end());
for (auto x: back_sol){
init_sol.push_back(x);
}
return init_sol;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
21204 KB |
Output is correct |
2 |
Correct |
11 ms |
21204 KB |
Output is correct |
3 |
Correct |
11 ms |
21204 KB |
Output is correct |
4 |
Correct |
11 ms |
21204 KB |
Output is correct |
5 |
Correct |
12 ms |
21204 KB |
Output is correct |
6 |
Correct |
11 ms |
21248 KB |
Output is correct |
7 |
Correct |
120 ms |
43076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
21204 KB |
Output is correct |
2 |
Correct |
11 ms |
21204 KB |
Output is correct |
3 |
Correct |
11 ms |
21204 KB |
Output is correct |
4 |
Correct |
12 ms |
21160 KB |
Output is correct |
5 |
Correct |
11 ms |
21204 KB |
Output is correct |
6 |
Correct |
138 ms |
38696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
21716 KB |
Output is correct |
2 |
Correct |
11 ms |
21204 KB |
Output is correct |
3 |
Correct |
11 ms |
21204 KB |
Output is correct |
4 |
Correct |
11 ms |
21204 KB |
Output is correct |
5 |
Correct |
12 ms |
21496 KB |
Output is correct |
6 |
Correct |
11 ms |
21204 KB |
Output is correct |
7 |
Correct |
13 ms |
21332 KB |
Output is correct |
8 |
Correct |
11 ms |
21204 KB |
Output is correct |
9 |
Correct |
12 ms |
21220 KB |
Output is correct |
10 |
Correct |
12 ms |
21460 KB |
Output is correct |
11 |
Correct |
12 ms |
21184 KB |
Output is correct |
12 |
Correct |
14 ms |
21460 KB |
Output is correct |
13 |
Correct |
11 ms |
21280 KB |
Output is correct |
14 |
Correct |
11 ms |
21256 KB |
Output is correct |
15 |
Correct |
11 ms |
21312 KB |
Output is correct |
16 |
Correct |
11 ms |
21204 KB |
Output is correct |
17 |
Correct |
82 ms |
32216 KB |
Output is correct |
18 |
Correct |
58 ms |
29996 KB |
Output is correct |
19 |
Correct |
11 ms |
21204 KB |
Output is correct |
20 |
Correct |
12 ms |
21204 KB |
Output is correct |
21 |
Correct |
14 ms |
21184 KB |
Output is correct |
22 |
Correct |
11 ms |
21204 KB |
Output is correct |
23 |
Correct |
134 ms |
38716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
21204 KB |
Output is correct |
2 |
Correct |
13 ms |
21716 KB |
Output is correct |
3 |
Correct |
175 ms |
40996 KB |
Output is correct |
4 |
Correct |
184 ms |
40868 KB |
Output is correct |
5 |
Correct |
13 ms |
21588 KB |
Output is correct |
6 |
Correct |
14 ms |
21716 KB |
Output is correct |
7 |
Correct |
11 ms |
21244 KB |
Output is correct |
8 |
Correct |
11 ms |
21204 KB |
Output is correct |
9 |
Correct |
11 ms |
21204 KB |
Output is correct |
10 |
Correct |
13 ms |
21568 KB |
Output is correct |
11 |
Correct |
13 ms |
21588 KB |
Output is correct |
12 |
Correct |
13 ms |
21716 KB |
Output is correct |
13 |
Correct |
13 ms |
21676 KB |
Output is correct |
14 |
Correct |
13 ms |
21716 KB |
Output is correct |
15 |
Correct |
14 ms |
21844 KB |
Output is correct |
16 |
Correct |
12 ms |
21460 KB |
Output is correct |
17 |
Correct |
11 ms |
21204 KB |
Output is correct |
18 |
Correct |
13 ms |
21716 KB |
Output is correct |
19 |
Correct |
14 ms |
21440 KB |
Output is correct |
20 |
Correct |
192 ms |
43256 KB |
Output is correct |
21 |
Correct |
183 ms |
40880 KB |
Output is correct |
22 |
Correct |
12 ms |
21496 KB |
Output is correct |
23 |
Correct |
11 ms |
21384 KB |
Output is correct |
24 |
Correct |
11 ms |
21204 KB |
Output is correct |
25 |
Correct |
12 ms |
21460 KB |
Output is correct |
26 |
Correct |
14 ms |
21588 KB |
Output is correct |
27 |
Correct |
179 ms |
42084 KB |
Output is correct |
28 |
Correct |
185 ms |
42040 KB |
Output is correct |
29 |
Correct |
11 ms |
21204 KB |
Output is correct |
30 |
Correct |
203 ms |
43076 KB |
Output is correct |
31 |
Correct |
15 ms |
21204 KB |
Output is correct |
32 |
Correct |
194 ms |
40872 KB |
Output is correct |
33 |
Correct |
180 ms |
42084 KB |
Output is correct |
34 |
Correct |
66 ms |
32220 KB |
Output is correct |
35 |
Correct |
11 ms |
21344 KB |
Output is correct |
36 |
Correct |
160 ms |
38800 KB |
Output is correct |
37 |
Correct |
162 ms |
42028 KB |
Output is correct |
38 |
Correct |
11 ms |
21460 KB |
Output is correct |
39 |
Correct |
156 ms |
38132 KB |
Output is correct |
40 |
Correct |
11 ms |
21448 KB |
Output is correct |
41 |
Correct |
196 ms |
43128 KB |
Output is correct |
42 |
Correct |
179 ms |
41996 KB |
Output is correct |
43 |
Correct |
11 ms |
21204 KB |
Output is correct |
44 |
Correct |
12 ms |
21696 KB |
Output is correct |
45 |
Correct |
11 ms |
21588 KB |
Output is correct |
46 |
Correct |
51 ms |
30024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
21204 KB |
Output is correct |
2 |
Correct |
11 ms |
21204 KB |
Output is correct |
3 |
Correct |
11 ms |
21204 KB |
Output is correct |
4 |
Correct |
11 ms |
21204 KB |
Output is correct |
5 |
Correct |
12 ms |
21204 KB |
Output is correct |
6 |
Correct |
11 ms |
21248 KB |
Output is correct |
7 |
Correct |
120 ms |
43076 KB |
Output is correct |
8 |
Correct |
11 ms |
21204 KB |
Output is correct |
9 |
Correct |
11 ms |
21204 KB |
Output is correct |
10 |
Correct |
11 ms |
21204 KB |
Output is correct |
11 |
Correct |
12 ms |
21160 KB |
Output is correct |
12 |
Correct |
11 ms |
21204 KB |
Output is correct |
13 |
Correct |
138 ms |
38696 KB |
Output is correct |
14 |
Correct |
16 ms |
21716 KB |
Output is correct |
15 |
Correct |
11 ms |
21204 KB |
Output is correct |
16 |
Correct |
11 ms |
21204 KB |
Output is correct |
17 |
Correct |
11 ms |
21204 KB |
Output is correct |
18 |
Correct |
12 ms |
21496 KB |
Output is correct |
19 |
Correct |
11 ms |
21204 KB |
Output is correct |
20 |
Correct |
13 ms |
21332 KB |
Output is correct |
21 |
Correct |
11 ms |
21204 KB |
Output is correct |
22 |
Correct |
12 ms |
21220 KB |
Output is correct |
23 |
Correct |
12 ms |
21460 KB |
Output is correct |
24 |
Correct |
12 ms |
21184 KB |
Output is correct |
25 |
Correct |
14 ms |
21460 KB |
Output is correct |
26 |
Correct |
11 ms |
21280 KB |
Output is correct |
27 |
Correct |
11 ms |
21256 KB |
Output is correct |
28 |
Correct |
11 ms |
21312 KB |
Output is correct |
29 |
Correct |
11 ms |
21204 KB |
Output is correct |
30 |
Correct |
82 ms |
32216 KB |
Output is correct |
31 |
Correct |
58 ms |
29996 KB |
Output is correct |
32 |
Correct |
11 ms |
21204 KB |
Output is correct |
33 |
Correct |
12 ms |
21204 KB |
Output is correct |
34 |
Correct |
14 ms |
21184 KB |
Output is correct |
35 |
Correct |
11 ms |
21204 KB |
Output is correct |
36 |
Correct |
134 ms |
38716 KB |
Output is correct |
37 |
Correct |
10 ms |
21280 KB |
Output is correct |
38 |
Correct |
10 ms |
21204 KB |
Output is correct |
39 |
Correct |
15 ms |
21300 KB |
Output is correct |
40 |
Correct |
11 ms |
21284 KB |
Output is correct |
41 |
Correct |
89 ms |
31120 KB |
Output is correct |
42 |
Correct |
13 ms |
21828 KB |
Output is correct |
43 |
Correct |
134 ms |
32184 KB |
Output is correct |
44 |
Correct |
103 ms |
32172 KB |
Output is correct |
45 |
Correct |
100 ms |
32236 KB |
Output is correct |
46 |
Correct |
10 ms |
21184 KB |
Output is correct |
47 |
Correct |
10 ms |
21248 KB |
Output is correct |
48 |
Correct |
10 ms |
21272 KB |
Output is correct |
49 |
Correct |
14 ms |
21480 KB |
Output is correct |
50 |
Correct |
142 ms |
38712 KB |
Output is correct |
51 |
Correct |
220 ms |
43084 KB |
Output is correct |
52 |
Correct |
226 ms |
43148 KB |
Output is correct |
53 |
Correct |
257 ms |
43444 KB |
Output is correct |
54 |
Correct |
254 ms |
43196 KB |
Output is correct |
55 |
Correct |
253 ms |
43172 KB |
Output is correct |
56 |
Correct |
280 ms |
43188 KB |
Output is correct |
57 |
Correct |
147 ms |
42588 KB |
Output is correct |
58 |
Correct |
178 ms |
39172 KB |
Output is correct |
59 |
Correct |
286 ms |
43324 KB |
Output is correct |
60 |
Correct |
321 ms |
43332 KB |
Output is correct |
61 |
Correct |
265 ms |
43300 KB |
Output is correct |
62 |
Correct |
41 ms |
24880 KB |
Output is correct |
63 |
Correct |
196 ms |
42160 KB |
Output is correct |
64 |
Correct |
180 ms |
32168 KB |
Output is correct |
65 |
Correct |
15 ms |
21196 KB |
Output is correct |
66 |
Correct |
20 ms |
21332 KB |
Output is correct |
67 |
Correct |
210 ms |
43664 KB |
Output is correct |
68 |
Correct |
334 ms |
43192 KB |
Output is correct |
69 |
Correct |
130 ms |
32308 KB |
Output is correct |
70 |
Correct |
14 ms |
21460 KB |
Output is correct |
71 |
Correct |
219 ms |
37716 KB |
Output is correct |
72 |
Correct |
15 ms |
21272 KB |
Output is correct |
73 |
Correct |
333 ms |
43164 KB |
Output is correct |
74 |
Correct |
179 ms |
38536 KB |
Output is correct |
75 |
Correct |
26 ms |
22308 KB |
Output is correct |
76 |
Correct |
90 ms |
29076 KB |
Output is correct |
77 |
Correct |
133 ms |
32296 KB |
Output is correct |
78 |
Correct |
341 ms |
43376 KB |
Output is correct |
79 |
Correct |
14 ms |
21204 KB |
Output is correct |
80 |
Correct |
360 ms |
47916 KB |
Output is correct |
81 |
Correct |
14 ms |
21468 KB |
Output is correct |
82 |
Correct |
237 ms |
43068 KB |
Output is correct |
83 |
Correct |
12 ms |
21332 KB |
Output is correct |
84 |
Correct |
13 ms |
21272 KB |
Output is correct |
85 |
Correct |
72 ms |
28728 KB |
Output is correct |
86 |
Correct |
12 ms |
21460 KB |
Output is correct |
87 |
Correct |
12 ms |
21716 KB |
Output is correct |
88 |
Correct |
16 ms |
21844 KB |
Output is correct |
89 |
Correct |
316 ms |
43340 KB |
Output is correct |
90 |
Correct |
287 ms |
43304 KB |
Output is correct |
91 |
Correct |
320 ms |
46296 KB |
Output is correct |
92 |
Correct |
14 ms |
21204 KB |
Output is correct |