#include "islands.h"
#include <variant>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=(int)n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=(int)n-1; i>=s; --i)
#define PB push_back
#define F first
#define S second
const int MAXN = 100010;
int n, m, uv, ue, cur, stpos[MAXN];
bool vis[MAXN], blocked[MAXN], inst[MAXN];
vector<int> st, se, stt, see, t1, t2, c1, c2, v1, v2, ans;
vector<pii> g[MAXN];
void build(vector<int>& stv, vector<int>& ste, int v, int e, vector<int>& c, vector<int>& t, vector<int>& a, int th){
int pos=0;
while(stv[pos]!=v) ++pos;
forsn(i, th, pos) t.PB(ste[i]);
forsn(i, pos, ste.size()) c.PB(ste[i]), a.PB(stv[i]);
c.PB(e);
a.PB(stv.back());
}
bool dfs2(int v){
inst[v]=true;
vis[v]=true;
stt.PB(v);
for(pii to:g[v]) if(!vis[to.F] && !blocked[to.F]) {
see.PB(to.S);
bool ret = dfs2(to.F);
if(ret) return true;
}
else if((inst[to.F] || stpos[to.F]!=-1) && !blocked[to.F] && to.S != se[cur]){
int loops;
build(st, se, uv, ue, c1, t1, v1, cur);
if(inst[to.F]){
loops=2;
build(stt, see, to.F, to.S, c2, t2, v2, 0);
}
else{
loops=1;
for(int el:see) t2.PB(el);
t2.PB(to.S);
int cp = stpos[to.F];
while(cp<stpos[uv]) t2.PB(se[cp]), ++cp;
int pos=0;
while(v1[pos]!=st[cp]) ++pos;
dforn(i, pos) c2.PB(c1[i]);
dforsn(i, pos, c1.size()) c2.PB(c1[i]);
}
forn(i, cur) ans.PB(se[i]);
forn(lo, loops){
for(int el:t1) ans.PB(el);
for(int el:c1) ans.PB(el);
dforn(i, t1.size()) ans.PB(t1[i]);
for(int el:t2) ans.PB(el);
for(int el:c2) ans.PB(el);
dforn(i, t2.size()) ans.PB(t2[i]);
reverse(c1.begin(), c1.end());
reverse(c2.begin(), c2.end());
}
dforn(i, cur) ans.PB(se[i]);
return true;
}
inst[v]=false;
stt.pop_back();
if(!see.empty()) see.pop_back();
return false;
}
int dfs1(int v){
stpos[v]=(int)st.size();
st.PB(v);
vis[v]=true;
for(pii to:g[v]) if(!vis[to.F] && !blocked[to.F]){
se.PB(to.S);
int ret = dfs1(to.F);
if(ret) return ret;
}
else if(stpos[to.F]!=-1){
uv = to.F, ue = to.S;
while(cur<=stpos[to.F]){
bool ret = dfs2(st[cur]);
if(ret) return 1;
blocked[st[cur]]=true;
++cur;
}
}
if((int)st.size() <= cur+1) return 2;
st.pop_back();
se.pop_back();
stpos[v]=-1;
return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
n=N, m=M;
forn(i, n) stpos[i]=-1;
forn(i, m) g[U[i]].PB({V[i], i});
int ret = dfs1(0);
if(ret==1) return ans;
else return false;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2588 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
28 ms |
7556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
28 ms |
6964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2772 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2796 KB |
Output is correct |
6 |
Correct |
1 ms |
2648 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2772 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
1 ms |
2644 KB |
Output is correct |
14 |
Correct |
1 ms |
2644 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
1 ms |
2644 KB |
Output is correct |
17 |
Correct |
15 ms |
5332 KB |
Output is correct |
18 |
Correct |
13 ms |
4948 KB |
Output is correct |
19 |
Correct |
1 ms |
2644 KB |
Output is correct |
20 |
Correct |
1 ms |
2644 KB |
Output is correct |
21 |
Correct |
1 ms |
2644 KB |
Output is correct |
22 |
Correct |
1 ms |
2644 KB |
Output is correct |
23 |
Correct |
24 ms |
6996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2772 KB |
Output is correct |
3 |
Correct |
25 ms |
7380 KB |
Output is correct |
4 |
Correct |
29 ms |
7508 KB |
Output is correct |
5 |
Correct |
2 ms |
2772 KB |
Output is correct |
6 |
Correct |
2 ms |
2772 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2900 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
2 ms |
2900 KB |
Output is correct |
14 |
Correct |
3 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2780 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
1 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2772 KB |
Output is correct |
19 |
Correct |
2 ms |
2644 KB |
Output is correct |
20 |
Correct |
28 ms |
8016 KB |
Output is correct |
21 |
Correct |
26 ms |
7508 KB |
Output is correct |
22 |
Correct |
1 ms |
2772 KB |
Output is correct |
23 |
Correct |
1 ms |
2644 KB |
Output is correct |
24 |
Correct |
1 ms |
2644 KB |
Output is correct |
25 |
Correct |
2 ms |
2644 KB |
Output is correct |
26 |
Correct |
2 ms |
2772 KB |
Output is correct |
27 |
Correct |
29 ms |
8020 KB |
Output is correct |
28 |
Correct |
33 ms |
8108 KB |
Output is correct |
29 |
Correct |
1 ms |
2644 KB |
Output is correct |
30 |
Correct |
34 ms |
8452 KB |
Output is correct |
31 |
Correct |
1 ms |
2644 KB |
Output is correct |
32 |
Correct |
27 ms |
8024 KB |
Output is correct |
33 |
Correct |
26 ms |
7612 KB |
Output is correct |
34 |
Correct |
15 ms |
5324 KB |
Output is correct |
35 |
Correct |
2 ms |
2772 KB |
Output is correct |
36 |
Correct |
24 ms |
7116 KB |
Output is correct |
37 |
Correct |
28 ms |
8244 KB |
Output is correct |
38 |
Correct |
2 ms |
2644 KB |
Output is correct |
39 |
Correct |
24 ms |
7124 KB |
Output is correct |
40 |
Correct |
2 ms |
2772 KB |
Output is correct |
41 |
Correct |
30 ms |
8436 KB |
Output is correct |
42 |
Correct |
27 ms |
8112 KB |
Output is correct |
43 |
Correct |
1 ms |
2644 KB |
Output is correct |
44 |
Correct |
2 ms |
2772 KB |
Output is correct |
45 |
Correct |
2 ms |
2772 KB |
Output is correct |
46 |
Correct |
13 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2588 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
28 ms |
7556 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
1 ms |
2644 KB |
Output is correct |
13 |
Correct |
28 ms |
6964 KB |
Output is correct |
14 |
Correct |
2 ms |
2772 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
1 ms |
2644 KB |
Output is correct |
17 |
Correct |
1 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2796 KB |
Output is correct |
19 |
Correct |
1 ms |
2648 KB |
Output is correct |
20 |
Correct |
1 ms |
2644 KB |
Output is correct |
21 |
Correct |
1 ms |
2644 KB |
Output is correct |
22 |
Correct |
1 ms |
2644 KB |
Output is correct |
23 |
Correct |
2 ms |
2772 KB |
Output is correct |
24 |
Correct |
1 ms |
2644 KB |
Output is correct |
25 |
Correct |
2 ms |
2772 KB |
Output is correct |
26 |
Correct |
1 ms |
2644 KB |
Output is correct |
27 |
Correct |
1 ms |
2644 KB |
Output is correct |
28 |
Correct |
1 ms |
2644 KB |
Output is correct |
29 |
Correct |
1 ms |
2644 KB |
Output is correct |
30 |
Correct |
15 ms |
5332 KB |
Output is correct |
31 |
Correct |
13 ms |
4948 KB |
Output is correct |
32 |
Correct |
1 ms |
2644 KB |
Output is correct |
33 |
Correct |
1 ms |
2644 KB |
Output is correct |
34 |
Correct |
1 ms |
2644 KB |
Output is correct |
35 |
Correct |
1 ms |
2644 KB |
Output is correct |
36 |
Correct |
24 ms |
6996 KB |
Output is correct |
37 |
Correct |
1 ms |
2644 KB |
Output is correct |
38 |
Correct |
1 ms |
2644 KB |
Output is correct |
39 |
Correct |
1 ms |
2656 KB |
Output is correct |
40 |
Correct |
1 ms |
2644 KB |
Output is correct |
41 |
Correct |
14 ms |
5028 KB |
Output is correct |
42 |
Correct |
2 ms |
2772 KB |
Output is correct |
43 |
Correct |
23 ms |
11248 KB |
Output is correct |
44 |
Correct |
23 ms |
9080 KB |
Output is correct |
45 |
Correct |
25 ms |
11420 KB |
Output is correct |
46 |
Correct |
1 ms |
2644 KB |
Output is correct |
47 |
Correct |
2 ms |
2644 KB |
Output is correct |
48 |
Correct |
1 ms |
2644 KB |
Output is correct |
49 |
Correct |
2 ms |
2772 KB |
Output is correct |
50 |
Correct |
68 ms |
22508 KB |
Output is correct |
51 |
Correct |
48 ms |
16880 KB |
Output is correct |
52 |
Correct |
49 ms |
18340 KB |
Output is correct |
53 |
Correct |
57 ms |
19820 KB |
Output is correct |
54 |
Correct |
47 ms |
15996 KB |
Output is correct |
55 |
Correct |
49 ms |
17596 KB |
Output is correct |
56 |
Correct |
49 ms |
16576 KB |
Output is correct |
57 |
Correct |
43 ms |
9040 KB |
Output is correct |
58 |
Correct |
60 ms |
20804 KB |
Output is correct |
59 |
Correct |
45 ms |
9476 KB |
Output is correct |
60 |
Correct |
44 ms |
10116 KB |
Output is correct |
61 |
Correct |
44 ms |
9620 KB |
Output is correct |
62 |
Correct |
8 ms |
4052 KB |
Output is correct |
63 |
Correct |
43 ms |
9260 KB |
Output is correct |
64 |
Correct |
17 ms |
5628 KB |
Output is correct |
65 |
Correct |
1 ms |
2644 KB |
Output is correct |
66 |
Correct |
2 ms |
2644 KB |
Output is correct |
67 |
Correct |
43 ms |
9984 KB |
Output is correct |
68 |
Correct |
29 ms |
8456 KB |
Output is correct |
69 |
Correct |
26 ms |
9856 KB |
Output is correct |
70 |
Correct |
2 ms |
2772 KB |
Output is correct |
71 |
Correct |
33 ms |
7600 KB |
Output is correct |
72 |
Correct |
2 ms |
2644 KB |
Output is correct |
73 |
Correct |
50 ms |
9220 KB |
Output is correct |
74 |
Correct |
62 ms |
22652 KB |
Output is correct |
75 |
Correct |
3 ms |
3028 KB |
Output is correct |
76 |
Correct |
25 ms |
10576 KB |
Output is correct |
77 |
Correct |
35 ms |
18412 KB |
Output is correct |
78 |
Correct |
43 ms |
10116 KB |
Output is correct |
79 |
Correct |
1 ms |
2644 KB |
Output is correct |
80 |
Correct |
69 ms |
17276 KB |
Output is correct |
81 |
Correct |
2 ms |
2772 KB |
Output is correct |
82 |
Correct |
26 ms |
7796 KB |
Output is correct |
83 |
Correct |
2 ms |
2644 KB |
Output is correct |
84 |
Correct |
1 ms |
2644 KB |
Output is correct |
85 |
Correct |
28 ms |
11452 KB |
Output is correct |
86 |
Correct |
2 ms |
2772 KB |
Output is correct |
87 |
Correct |
2 ms |
3028 KB |
Output is correct |
88 |
Correct |
2 ms |
2772 KB |
Output is correct |
89 |
Correct |
43 ms |
10112 KB |
Output is correct |
90 |
Correct |
41 ms |
9620 KB |
Output is correct |
91 |
Correct |
58 ms |
16580 KB |
Output is correct |
92 |
Correct |
1 ms |
2644 KB |
Output is correct |