#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void add(vector<int> &A, vector<int> &B, int rev = 0){
if(!rev) for(auto x: B) A.push_back(x);
else for(int i=(int)B.size()-1; i>=0; i--) A.push_back(B[i]);
}
int n, m;
multiset<int> link[100002], revLink[100002];
bool removeUselessVertices();
vector<int> solve();
multimap<pair<int, int>, int> edgeMap;
multimap<pair<int, int>, int> edgeMap2;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){
n = N, m = M;
for(int i=0; i<m; i++){
link[U[i]].insert(V[i]);
revLink[V[i]].insert(U[i]);
}
if(removeUselessVertices()) return false;
vector<int> ret;
vector<int> ans = solve();
for(int i=0; i<m; i++) edgeMap.insert(make_pair(make_pair(U[i], V[i]), i));
for(int i=0; i<(int)ans.size()-1; i++){
int x = ans[i], y = ans[i+1];
auto it = edgeMap2.find(make_pair(x, y));
if(it != edgeMap2.end() && it->first == make_pair(x, y) &&
(!(!ret.empty() && ret.back() == it->second) ||
(next(it) != edgeMap2.end() && next(it)->first == make_pair(x, y)))){
if(!ret.empty() && ret.back() == it->second) ++it;
ret.push_back(it->second);
edgeMap2.erase(it);
edgeMap.insert(make_pair(make_pair(y, x), ret.back()));
}
else{
it = edgeMap.find(make_pair(x, y));
if(!ret.empty() && ret.back() == it->second) ++it;
ret.push_back(it->second);
edgeMap.erase(it);
edgeMap2.insert(make_pair(make_pair(y, x), ret.back()));
}
}
return ret;
}
int deg[100002];
bool removed[100002];
bool seenAsStart[100002];
int s = 0;
vector<int> startList;
bool removeUselessVertices(){
/// outdegree 0 삭제
queue<int> que;
for(int i=0; i<n; i++){
deg[i] = (int)link[i].size();
if(!deg[i] && !removed[i]) removed[i] = 1, que.push(i);
}
while(deg[s] == 1){
for(auto y: revLink[s]){
link[y].erase(link[y].find(s));
deg[y]--;
if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
}
revLink[s].clear();
startList.push_back(s);
int ns = *link[s].begin();
link[s].erase(link[s].find(ns));
revLink[ns].erase(revLink[ns].find(s));
s = ns;
}
while(!que.empty()){
int x = que.front(); que.pop();
deg[x] = 0;
if(x==s) return 1;
for(auto y: revLink[x]){
deg[y]--;
link[y].erase(link[y].find(x));
if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
while(deg[s] == 1){
for(auto y: revLink[s]){
link[y].erase(link[y].find(s));
deg[y]--;
if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
}
revLink[s].clear();
startList.push_back(s);
int ns = *link[s].begin();
link[s].erase(link[s].find(ns));
revLink[ns].erase(revLink[ns].find(s));
s = ns;
if(removed[ns]) return 1;
}
}
}
if(removed[s]) return true;
return false;
}
int A = -1, B = -1;
bool visited[100002];
bool visitedinA[100002];
bool search_mode = 0;
bool search_overlap = 0;
void justSearch(int x){
visited[x] = 1;
if(search_mode == 0 && x != s) visitedinA[x] = 1;
for(auto y: link[x]){
if(x==s && y!=A && y!=B) continue;
if(x==s && y==B) search_mode = 1;
if(visited[y]){
if(search_mode && visitedinA[y]) search_overlap = 1;
continue;
}
justSearch(y);
}
}
vector<int> rec;
bool findCycle(int x, int lead, vector<int> &path, vector<int> &cycle, bool ina=0){
if(x==s) rec.clear();
visited[x] = 1;
rec.push_back(x);
for(auto y: link[x]){
if(x==s && y!=lead) continue;
if(visited[y]){
if(!ina || (y==0 && visitedinA[x]) || visitedinA[y]){
int c = find(rec.begin(), rec.end(), y) - rec.begin();
for(int i=0; i<=c; i++) path.push_back(rec[i]);
for(int i=c+1; i<(int)rec.size(); i++) cycle.push_back(rec[i]);
return true;
}
continue;
}
if(findCycle(y, lead, path, cycle, ina)) return true;
}
rec.pop_back();
return false;
}
bool inCycle[100002];
vector<int> record;
bool findInCycle(int x, int lead, vector<int> &path){
visited[x] = 1;
record.push_back(x);
for(auto y: link[x]){
if(x==s && y!=lead) continue;
if(inCycle[y] && y!=s){
for(auto z: record){
path.push_back(z);
}
path.push_back(y);
return true;
}
if(visited[y]) continue;
if(findInCycle(y, lead, path)) return true;
}
record.pop_back();
return false;
}
vector<int> solve(){
vector<int> ret;
if((int)link[s].size() <= 1) exit(1);
assert((int)link[s].size() > 1);
A = *link[s].begin();
B = *next(link[s].begin());
justSearch(s);
/// Case 2. A=B
if(A==B){
vector<int> pathA, cycleA;
memset(visited, 0, sizeof(visited));
findCycle(s, A, pathA, cycleA);
cycleA.insert(cycleA.begin(), pathA.back());
pathA.pop_back();
if(find(cycleA.begin(), cycleA.end(), s) == cycleA.end()){ /// 시작점이 포함되지 않음
int c = cycleA[0];
add(ret, startList);
add(ret, pathA); add(ret, cycleA); ret.push_back(c); add(ret, pathA, 1); ret.pop_back();
add(ret, pathA); ret.push_back(c); add(ret, cycleA, 1); add(ret, pathA, 1);
add(ret, startList, 1);
return ret;
}
else{
add(ret, startList);
add(ret, pathA); add(ret, cycleA);
ret.push_back(s);
int idx = find(cycleA.begin(), cycleA.end(), B) - cycleA.begin();
for(int i=idx; i>=0; i--) ret.push_back(cycleA[i]);
for(int i=(int)cycleA.size()-1; i>=idx; i--) ret.push_back(cycleA[i]);
ret.push_back(s);
add(ret, startList, 1);
return ret;
}
}
/// Case 1. A -> B의 경로가 없다
if(!visitedinA[B] && !search_overlap){
/// 각각 사이클 찾기
vector<int> pathA, cycleA, pathB, cycleB;
memset(visited, 0, sizeof(visited));
findCycle(s, A, pathA, cycleA);
memset(visited, 0, sizeof(visited));
findCycle(s, B, pathB, cycleB);
add(ret, startList);
add(ret, pathA);
add(ret, cycleA);
add(ret, pathA, 1);
ret.pop_back();
add(ret, pathB);
add(ret, cycleB);
add(ret, pathB, 1);
ret.pop_back();
add(ret, pathA);
add(ret, cycleA, 1);
add(ret, pathA, 1);
ret.pop_back();
add(ret, pathB);
add(ret, cycleB, 1);
add(ret, pathB, 1);
add(ret, startList, 1);
return ret;
}
/// Case 3. A->B의 경로가 있다
vector<int> pathB, cycleB;
memset(visited, 0, sizeof(visited));
findCycle(s, B, pathB, cycleB, 1);
cycleB.insert(cycleB.begin(), pathB.back());
pathB.pop_back();
if(find(cycleB.begin(), cycleB.end(), s) == cycleB.end()){ /// 시작점이 포함되지 않은 사이클
for(auto x: cycleB) inCycle[x] = 1;
add(ret, startList);
add(ret, pathB);
add(ret, cycleB);
ret.push_back(cycleB[0]);
add(ret, pathB, 1);
vector<int> pathA;
memset(visited, 0, sizeof(visited));
findInCycle(s, A, pathA);
int c = pathA.back();
pathA.pop_back();
ret.pop_back();
add(ret, pathA);
int idx = find(cycleB.begin(), cycleB.end(), c) - cycleB.begin();
for(int i=idx; i>=0; i--) ret.push_back(cycleB[i]);
for(int i=(int)cycleB.size()-1; i>=idx; i--) ret.push_back(cycleB[i]);
add(ret, pathA, 1);
add(ret, startList, 1);
return ret;
}
/// 시작점이 포함된 사이클
for(auto x: cycleB) inCycle[x] = 1;
add(ret, startList);
add(ret, cycleB);
vector<int> pathA;
memset(visited, 0, sizeof(visited));
findInCycle(s, A, pathA);
int c = pathA.back();
pathA.pop_back();
add(ret, pathA);
int idx = find(cycleB.begin(), cycleB.end(), c) - cycleB.begin();
for(int i=idx; i>=0; i--) ret.push_back(cycleB[i]);
for(int i=(int)cycleB.size()-1; i>=idx; i--) ret.push_back(cycleB[i]);
add(ret, pathA, 1);
add(ret, startList, 1);
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
156 ms |
44120 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 |
5 ms |
9704 KB |
Output is correct |
4 |
Correct |
4 ms |
9812 KB |
Output is correct |
5 |
Correct |
5 ms |
9736 KB |
Output is correct |
6 |
Correct |
198 ms |
37312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
10452 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
7 ms |
9940 KB |
Output is correct |
6 |
Correct |
4 ms |
9812 KB |
Output is correct |
7 |
Correct |
5 ms |
9824 KB |
Output is correct |
8 |
Correct |
5 ms |
9812 KB |
Output is correct |
9 |
Correct |
5 ms |
9844 KB |
Output is correct |
10 |
Correct |
6 ms |
10068 KB |
Output is correct |
11 |
Correct |
5 ms |
9812 KB |
Output is correct |
12 |
Correct |
6 ms |
9988 KB |
Output is correct |
13 |
Correct |
4 ms |
9684 KB |
Output is correct |
14 |
Correct |
5 ms |
9684 KB |
Output is correct |
15 |
Correct |
5 ms |
9812 KB |
Output is correct |
16 |
Correct |
4 ms |
9684 KB |
Output is correct |
17 |
Correct |
101 ms |
27000 KB |
Output is correct |
18 |
Correct |
79 ms |
23628 KB |
Output is correct |
19 |
Correct |
5 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9740 KB |
Output is correct |
21 |
Correct |
5 ms |
9812 KB |
Output is correct |
22 |
Correct |
5 ms |
9824 KB |
Output is correct |
23 |
Correct |
234 ms |
37236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9812 KB |
Output is correct |
2 |
Correct |
9 ms |
10452 KB |
Output is correct |
3 |
Correct |
242 ms |
40676 KB |
Output is correct |
4 |
Correct |
227 ms |
40704 KB |
Output is correct |
5 |
Correct |
7 ms |
10452 KB |
Output is correct |
6 |
Correct |
7 ms |
10452 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9812 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
7 ms |
10196 KB |
Output is correct |
11 |
Correct |
6 ms |
10068 KB |
Output is correct |
12 |
Correct |
7 ms |
10452 KB |
Output is correct |
13 |
Correct |
8 ms |
10544 KB |
Output is correct |
14 |
Correct |
7 ms |
10452 KB |
Output is correct |
15 |
Correct |
9 ms |
10836 KB |
Output is correct |
16 |
Correct |
6 ms |
10068 KB |
Output is correct |
17 |
Correct |
5 ms |
9684 KB |
Output is correct |
18 |
Correct |
7 ms |
10512 KB |
Output is correct |
19 |
Correct |
7 ms |
10152 KB |
Output is correct |
20 |
Correct |
192 ms |
31728 KB |
Output is correct |
21 |
Correct |
244 ms |
40740 KB |
Output is correct |
22 |
Correct |
5 ms |
9812 KB |
Output is correct |
23 |
Correct |
5 ms |
9812 KB |
Output is correct |
24 |
Correct |
5 ms |
9684 KB |
Output is correct |
25 |
Correct |
6 ms |
10068 KB |
Output is correct |
26 |
Correct |
7 ms |
10196 KB |
Output is correct |
27 |
Correct |
240 ms |
42428 KB |
Output is correct |
28 |
Correct |
258 ms |
42504 KB |
Output is correct |
29 |
Correct |
5 ms |
9684 KB |
Output is correct |
30 |
Correct |
225 ms |
31640 KB |
Output is correct |
31 |
Correct |
4 ms |
9812 KB |
Output is correct |
32 |
Correct |
246 ms |
40812 KB |
Output is correct |
33 |
Correct |
239 ms |
42472 KB |
Output is correct |
34 |
Correct |
86 ms |
27012 KB |
Output is correct |
35 |
Correct |
6 ms |
10068 KB |
Output is correct |
36 |
Correct |
206 ms |
37336 KB |
Output is correct |
37 |
Correct |
228 ms |
42544 KB |
Output is correct |
38 |
Correct |
5 ms |
9812 KB |
Output is correct |
39 |
Correct |
135 ms |
26536 KB |
Output is correct |
40 |
Correct |
6 ms |
10132 KB |
Output is correct |
41 |
Correct |
242 ms |
31620 KB |
Output is correct |
42 |
Correct |
247 ms |
42504 KB |
Output is correct |
43 |
Correct |
5 ms |
9684 KB |
Output is correct |
44 |
Correct |
6 ms |
10148 KB |
Output is correct |
45 |
Correct |
7 ms |
10196 KB |
Output is correct |
46 |
Correct |
65 ms |
23544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
156 ms |
44120 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
4 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9704 KB |
Output is correct |
11 |
Correct |
4 ms |
9812 KB |
Output is correct |
12 |
Correct |
5 ms |
9736 KB |
Output is correct |
13 |
Correct |
198 ms |
37312 KB |
Output is correct |
14 |
Correct |
9 ms |
10452 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
4 ms |
9684 KB |
Output is correct |
18 |
Correct |
7 ms |
9940 KB |
Output is correct |
19 |
Correct |
4 ms |
9812 KB |
Output is correct |
20 |
Correct |
5 ms |
9824 KB |
Output is correct |
21 |
Correct |
5 ms |
9812 KB |
Output is correct |
22 |
Correct |
5 ms |
9844 KB |
Output is correct |
23 |
Correct |
6 ms |
10068 KB |
Output is correct |
24 |
Correct |
5 ms |
9812 KB |
Output is correct |
25 |
Correct |
6 ms |
9988 KB |
Output is correct |
26 |
Correct |
4 ms |
9684 KB |
Output is correct |
27 |
Correct |
5 ms |
9684 KB |
Output is correct |
28 |
Correct |
5 ms |
9812 KB |
Output is correct |
29 |
Correct |
4 ms |
9684 KB |
Output is correct |
30 |
Correct |
101 ms |
27000 KB |
Output is correct |
31 |
Correct |
79 ms |
23628 KB |
Output is correct |
32 |
Correct |
5 ms |
9684 KB |
Output is correct |
33 |
Correct |
5 ms |
9740 KB |
Output is correct |
34 |
Correct |
5 ms |
9812 KB |
Output is correct |
35 |
Correct |
5 ms |
9824 KB |
Output is correct |
36 |
Correct |
234 ms |
37236 KB |
Output is correct |
37 |
Correct |
4 ms |
9684 KB |
Output is correct |
38 |
Correct |
5 ms |
9716 KB |
Output is correct |
39 |
Correct |
7 ms |
9732 KB |
Output is correct |
40 |
Correct |
6 ms |
9812 KB |
Output is correct |
41 |
Correct |
93 ms |
19488 KB |
Output is correct |
42 |
Correct |
7 ms |
10152 KB |
Output is correct |
43 |
Correct |
107 ms |
20792 KB |
Output is correct |
44 |
Correct |
103 ms |
20792 KB |
Output is correct |
45 |
Correct |
145 ms |
27156 KB |
Output is correct |
46 |
Correct |
5 ms |
9684 KB |
Output is correct |
47 |
Correct |
5 ms |
9684 KB |
Output is correct |
48 |
Correct |
5 ms |
9684 KB |
Output is correct |
49 |
Correct |
6 ms |
10016 KB |
Output is correct |
50 |
Correct |
426 ms |
32480 KB |
Output is correct |
51 |
Correct |
245 ms |
32128 KB |
Output is correct |
52 |
Correct |
249 ms |
32004 KB |
Output is correct |
53 |
Correct |
354 ms |
44672 KB |
Output is correct |
54 |
Correct |
245 ms |
32076 KB |
Output is correct |
55 |
Correct |
272 ms |
32012 KB |
Output is correct |
56 |
Correct |
339 ms |
44672 KB |
Output is correct |
57 |
Correct |
308 ms |
43696 KB |
Output is correct |
58 |
Correct |
368 ms |
36720 KB |
Output is correct |
59 |
Correct |
234 ms |
34544 KB |
Output is correct |
60 |
Correct |
229 ms |
34560 KB |
Output is correct |
61 |
Correct |
236 ms |
34632 KB |
Output is correct |
62 |
Correct |
22 ms |
13780 KB |
Output is correct |
63 |
Correct |
148 ms |
33228 KB |
Output is correct |
64 |
Correct |
141 ms |
25636 KB |
Output is correct |
65 |
Correct |
5 ms |
9812 KB |
Output is correct |
66 |
Correct |
6 ms |
9940 KB |
Output is correct |
67 |
Correct |
280 ms |
48364 KB |
Output is correct |
68 |
Correct |
274 ms |
33100 KB |
Output is correct |
69 |
Correct |
111 ms |
22624 KB |
Output is correct |
70 |
Correct |
7 ms |
10196 KB |
Output is correct |
71 |
Correct |
155 ms |
28024 KB |
Output is correct |
72 |
Correct |
6 ms |
9812 KB |
Output is correct |
73 |
Correct |
225 ms |
34320 KB |
Output is correct |
74 |
Correct |
302 ms |
36836 KB |
Output is correct |
75 |
Correct |
13 ms |
11388 KB |
Output is correct |
76 |
Correct |
107 ms |
23256 KB |
Output is correct |
77 |
Correct |
100 ms |
22856 KB |
Output is correct |
78 |
Correct |
242 ms |
34556 KB |
Output is correct |
79 |
Correct |
6 ms |
9704 KB |
Output is correct |
80 |
Correct |
580 ms |
51196 KB |
Output is correct |
81 |
Correct |
7 ms |
10068 KB |
Output is correct |
82 |
Correct |
188 ms |
32372 KB |
Output is correct |
83 |
Correct |
6 ms |
9880 KB |
Output is correct |
84 |
Correct |
5 ms |
9872 KB |
Output is correct |
85 |
Correct |
127 ms |
22676 KB |
Output is correct |
86 |
Correct |
7 ms |
10104 KB |
Output is correct |
87 |
Correct |
7 ms |
10580 KB |
Output is correct |
88 |
Correct |
9 ms |
10648 KB |
Output is correct |
89 |
Correct |
239 ms |
34560 KB |
Output is correct |
90 |
Correct |
222 ms |
34528 KB |
Output is correct |
91 |
Correct |
498 ms |
49660 KB |
Output is correct |
92 |
Correct |
5 ms |
9684 KB |
Output is correct |