#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,m;
vector<ii> al[200005];
ii edges[200005];
bool down[200005];
bool vis[200005];
bool onstk[200005];
int in[200005];
ii mx[200005];
int pp[200005];
int CTIME=1;
void dfs(int i){
vis[i]=true;
onstk[i]=true;
in[i]=CTIME++;
mx[i]=ii(-1,-1);
for (auto [it,id]:al[i]){
if (!vis[it]){
pp[it]=id;
dfs(it);
down[id]=true;
}
if (onstk[it]){
mx[i]=max(mx[i],{in[it],id});
}
else{
mx[i]=max(mx[i],mx[it]);
down[id]=true;
}
}
onstk[i]=false;
}
;
bool get(int i,vector<int> &v){
vis[i]=true;
onstk[i]=true;
for (auto [it,id]:al[i]){
if (!vis[it]){
if (get(it,v)){
v.pub(id);
return true;
}
}
if (onstk[it]){
v.pub(id);
return true;
}
}
onstk[i]=false;
return false;
}
variant<bool, vector<signed>> find_journey(
signed N, signed M, vector<signed> U, vector<signed> V) {
n=N,m=M;
rep(x,0,m){
al[U[x]].pub({V[x],x});
edges[x]={U[x],V[x]};
}
dfs(0);
//rep(x,0,n) cout<<in[x]<<" "; cout<<endl;
//rep(x,0,n) cout<<mx[x]<<" "; cout<<endl;
//rep(x,0,n) cout<<pp[x]<<" "; cout<<endl;
rep(x,0,n) if (vis[x]){
vector<ii> v;
for (auto [it,id]:al[x]) if (down[id] && mx[it].fi>=in[x]) v.pub({it,id});
if (sz(v)>=2){
vector<int> head;
int curr=x;
while (curr){
head.pub(pp[curr]);
curr=edges[pp[curr]].fi;
}
vector<signed> ans;
rep(x,sz(head),0) ans.pub(head[x]);
while (sz(v)>2) v.pob();
vector<int> tail[2],cyc[2];
rep(y,0,2){
memset(vis,false,sizeof(vis));
memset(onstk,false,sizeof(onstk));
onstk[x]=true;
for (auto it:head) vis[edges[it].fi]=true;
vis[x]=true;
vector<int> idx;
get(v[y].fi,idx);
idx.pub(v[y].se);
reverse(all(idx));
vector<int> idx1,idx2;
bool f=true;
for (auto it:idx){
if (edges[it].fi==edges[idx.back()].se) f=false;
if (f) tail[y].pub(it);
else cyc[y].pub(it);
}
//cout<<"debug: "<<v[y].fi<<endl;
//for (auto it:tail[y]) cout<<it<<" "; cout<<endl;
//for (auto it:cyc[y]) cout<<it<<" "; cout<<endl;
}
set<int> s;
rep(x,0,2) for (auto it:cyc[x]) s.insert(it);
if (sz(s)==sz(cyc[0])+sz(cyc[1])){
rep(x,0,4){
rep(y,0,sz(tail[x%2])) ans.pub(tail[x%2][y]);
if (x/2==0){
rep(y,0,sz(cyc[x%2])) ans.pub(cyc[x%2][y]);
}
else{
rep(y,sz(cyc[x%2]),0) ans.pub(cyc[x%2][y]);
}
rep(y,sz(tail[x%2]),0) ans.pub(tail[x%2][y]);
}
}
else{
s.clear();
for (auto it:cyc[0]) s.insert(it);
vector<int> tail2[2];
rep(x,0,2){
vector<int> temp;
for (auto it:tail[x]) temp.pub(it);
for (auto it:cyc[x]) temp.pub(it);
for (auto it:temp){
tail2[x].pub(it);
if (s.count(it)) break;
}
}
//cout<<"testing: "<<endl;
//for (auto it:tail2[0]) cout<<it<<" "; cout<<endl;
//for (auto it:tail2[1]) cout<<it<<" "; cout<<endl;
//for (auto it:cyc[0]) cout<<it<<" "; cout<<endl;
rep(x,0,sz(tail2[0])-1) ans.pub(tail2[0][x]);
rep(i,0,sz(cyc[0])) if (cyc[0][i]==tail2[0].back()){
rep(x,i,sz(cyc[0])) ans.pub(cyc[0][x]);
rep(x,0,i) ans.pub(cyc[0][x]);
}
rep(x,sz(tail2[0])-1,0) ans.pub(tail2[0][x]);
rep(x,0,sz(tail2[1])-1) ans.pub(tail2[1][x]);
rep(i,0,sz(cyc[0])) if (cyc[0][i]==tail2[1].back()){
rep(x,i,0) ans.pub(cyc[0][x]);
rep(x,sz(cyc[0]),i) ans.pub(cyc[0][x]);
}
rep(x,sz(tail2[1])-1,0) ans.pub(tail2[1][x]);
}
rep(x,0,sz(head)) ans.pub(head[x]);
return ans;
}
}
return false;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5332 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
4 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
5332 KB |
Output is correct |
7 |
Correct |
43 ms |
17696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5332 KB |
Output is correct |
2 |
Correct |
3 ms |
5048 KB |
Output is correct |
3 |
Correct |
3 ms |
5332 KB |
Output is correct |
4 |
Correct |
3 ms |
5332 KB |
Output is correct |
5 |
Correct |
3 ms |
5332 KB |
Output is correct |
6 |
Correct |
38 ms |
14560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5716 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
4 ms |
5332 KB |
Output is correct |
5 |
Correct |
3 ms |
5204 KB |
Output is correct |
6 |
Correct |
3 ms |
5332 KB |
Output is correct |
7 |
Correct |
3 ms |
5076 KB |
Output is correct |
8 |
Correct |
3 ms |
5460 KB |
Output is correct |
9 |
Correct |
4 ms |
5460 KB |
Output is correct |
10 |
Correct |
4 ms |
5716 KB |
Output is correct |
11 |
Correct |
3 ms |
5332 KB |
Output is correct |
12 |
Correct |
4 ms |
5716 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
5460 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
25 ms |
10936 KB |
Output is correct |
18 |
Correct |
20 ms |
10392 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
5332 KB |
Output is correct |
21 |
Correct |
3 ms |
5332 KB |
Output is correct |
22 |
Correct |
3 ms |
5332 KB |
Output is correct |
23 |
Correct |
39 ms |
14200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5332 KB |
Output is correct |
2 |
Correct |
4 ms |
5552 KB |
Output is correct |
3 |
Correct |
40 ms |
14876 KB |
Output is correct |
4 |
Correct |
36 ms |
15436 KB |
Output is correct |
5 |
Correct |
3 ms |
5588 KB |
Output is correct |
6 |
Correct |
5 ms |
5588 KB |
Output is correct |
7 |
Correct |
4 ms |
5332 KB |
Output is correct |
8 |
Correct |
3 ms |
5332 KB |
Output is correct |
9 |
Correct |
4 ms |
5416 KB |
Output is correct |
10 |
Correct |
4 ms |
5648 KB |
Output is correct |
11 |
Correct |
3 ms |
5332 KB |
Output is correct |
12 |
Correct |
4 ms |
5588 KB |
Output is correct |
13 |
Correct |
4 ms |
5844 KB |
Output is correct |
14 |
Correct |
4 ms |
5588 KB |
Output is correct |
15 |
Correct |
4 ms |
5716 KB |
Output is correct |
16 |
Correct |
3 ms |
5588 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
4 ms |
5588 KB |
Output is correct |
19 |
Correct |
3 ms |
5460 KB |
Output is correct |
20 |
Correct |
38 ms |
15668 KB |
Output is correct |
21 |
Correct |
37 ms |
15268 KB |
Output is correct |
22 |
Correct |
3 ms |
5204 KB |
Output is correct |
23 |
Correct |
3 ms |
5076 KB |
Output is correct |
24 |
Correct |
3 ms |
4964 KB |
Output is correct |
25 |
Correct |
3 ms |
5460 KB |
Output is correct |
26 |
Correct |
4 ms |
5716 KB |
Output is correct |
27 |
Correct |
53 ms |
16356 KB |
Output is correct |
28 |
Correct |
40 ms |
16364 KB |
Output is correct |
29 |
Correct |
2 ms |
4948 KB |
Output is correct |
30 |
Correct |
42 ms |
16764 KB |
Output is correct |
31 |
Correct |
3 ms |
5332 KB |
Output is correct |
32 |
Correct |
41 ms |
16076 KB |
Output is correct |
33 |
Correct |
46 ms |
15444 KB |
Output is correct |
34 |
Correct |
22 ms |
10964 KB |
Output is correct |
35 |
Correct |
3 ms |
5588 KB |
Output is correct |
36 |
Correct |
33 ms |
14472 KB |
Output is correct |
37 |
Correct |
44 ms |
16604 KB |
Output is correct |
38 |
Correct |
3 ms |
5076 KB |
Output is correct |
39 |
Correct |
33 ms |
13920 KB |
Output is correct |
40 |
Correct |
3 ms |
5588 KB |
Output is correct |
41 |
Correct |
43 ms |
16696 KB |
Output is correct |
42 |
Correct |
40 ms |
16496 KB |
Output is correct |
43 |
Correct |
3 ms |
4948 KB |
Output is correct |
44 |
Correct |
4 ms |
5204 KB |
Output is correct |
45 |
Correct |
4 ms |
5756 KB |
Output is correct |
46 |
Correct |
23 ms |
10220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5332 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
4 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
5332 KB |
Output is correct |
7 |
Correct |
43 ms |
17696 KB |
Output is correct |
8 |
Correct |
3 ms |
5332 KB |
Output is correct |
9 |
Correct |
3 ms |
5048 KB |
Output is correct |
10 |
Correct |
3 ms |
5332 KB |
Output is correct |
11 |
Correct |
3 ms |
5332 KB |
Output is correct |
12 |
Correct |
3 ms |
5332 KB |
Output is correct |
13 |
Correct |
38 ms |
14560 KB |
Output is correct |
14 |
Correct |
4 ms |
5716 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
5076 KB |
Output is correct |
17 |
Correct |
4 ms |
5332 KB |
Output is correct |
18 |
Correct |
3 ms |
5204 KB |
Output is correct |
19 |
Correct |
3 ms |
5332 KB |
Output is correct |
20 |
Correct |
3 ms |
5076 KB |
Output is correct |
21 |
Correct |
3 ms |
5460 KB |
Output is correct |
22 |
Correct |
4 ms |
5460 KB |
Output is correct |
23 |
Correct |
4 ms |
5716 KB |
Output is correct |
24 |
Correct |
3 ms |
5332 KB |
Output is correct |
25 |
Correct |
4 ms |
5716 KB |
Output is correct |
26 |
Correct |
3 ms |
4948 KB |
Output is correct |
27 |
Correct |
3 ms |
4948 KB |
Output is correct |
28 |
Correct |
3 ms |
5460 KB |
Output is correct |
29 |
Correct |
3 ms |
4948 KB |
Output is correct |
30 |
Correct |
25 ms |
10936 KB |
Output is correct |
31 |
Correct |
20 ms |
10392 KB |
Output is correct |
32 |
Correct |
3 ms |
4948 KB |
Output is correct |
33 |
Correct |
3 ms |
5332 KB |
Output is correct |
34 |
Correct |
3 ms |
5332 KB |
Output is correct |
35 |
Correct |
3 ms |
5332 KB |
Output is correct |
36 |
Correct |
39 ms |
14200 KB |
Output is correct |
37 |
Correct |
3 ms |
5332 KB |
Output is correct |
38 |
Correct |
2 ms |
4948 KB |
Output is correct |
39 |
Correct |
4 ms |
5048 KB |
Output is correct |
40 |
Correct |
3 ms |
5076 KB |
Output is correct |
41 |
Correct |
19 ms |
9820 KB |
Output is correct |
42 |
Correct |
4 ms |
5360 KB |
Output is correct |
43 |
Correct |
34 ms |
17088 KB |
Output is correct |
44 |
Correct |
45 ms |
15008 KB |
Output is correct |
45 |
Correct |
34 ms |
17432 KB |
Output is correct |
46 |
Correct |
3 ms |
5332 KB |
Output is correct |
47 |
Correct |
3 ms |
5332 KB |
Output is correct |
48 |
Correct |
3 ms |
5332 KB |
Output is correct |
49 |
Correct |
4 ms |
5588 KB |
Output is correct |
50 |
Correct |
134 ms |
30472 KB |
Output is correct |
51 |
Correct |
74 ms |
26428 KB |
Output is correct |
52 |
Correct |
79 ms |
27552 KB |
Output is correct |
53 |
Correct |
72 ms |
29484 KB |
Output is correct |
54 |
Correct |
80 ms |
25276 KB |
Output is correct |
55 |
Correct |
80 ms |
26796 KB |
Output is correct |
56 |
Correct |
81 ms |
26144 KB |
Output is correct |
57 |
Correct |
54 ms |
19000 KB |
Output is correct |
58 |
Correct |
103 ms |
23500 KB |
Output is correct |
59 |
Correct |
104 ms |
19756 KB |
Output is correct |
60 |
Correct |
63 ms |
20156 KB |
Output is correct |
61 |
Correct |
66 ms |
17072 KB |
Output is correct |
62 |
Correct |
15 ms |
7048 KB |
Output is correct |
63 |
Correct |
72 ms |
15836 KB |
Output is correct |
64 |
Correct |
25 ms |
11432 KB |
Output is correct |
65 |
Correct |
3 ms |
5332 KB |
Output is correct |
66 |
Correct |
3 ms |
5460 KB |
Output is correct |
67 |
Correct |
79 ms |
23036 KB |
Output is correct |
68 |
Correct |
54 ms |
16700 KB |
Output is correct |
69 |
Correct |
42 ms |
17540 KB |
Output is correct |
70 |
Correct |
4 ms |
5716 KB |
Output is correct |
71 |
Correct |
65 ms |
15336 KB |
Output is correct |
72 |
Correct |
4 ms |
5332 KB |
Output is correct |
73 |
Correct |
76 ms |
18864 KB |
Output is correct |
74 |
Correct |
131 ms |
28224 KB |
Output is correct |
75 |
Correct |
7 ms |
6100 KB |
Output is correct |
76 |
Correct |
40 ms |
15452 KB |
Output is correct |
77 |
Correct |
58 ms |
25676 KB |
Output is correct |
78 |
Correct |
69 ms |
20268 KB |
Output is correct |
79 |
Correct |
3 ms |
5332 KB |
Output is correct |
80 |
Correct |
129 ms |
27616 KB |
Output is correct |
81 |
Correct |
3 ms |
5588 KB |
Output is correct |
82 |
Correct |
40 ms |
15376 KB |
Output is correct |
83 |
Correct |
3 ms |
5460 KB |
Output is correct |
84 |
Correct |
3 ms |
5332 KB |
Output is correct |
85 |
Correct |
52 ms |
15380 KB |
Output is correct |
86 |
Correct |
3 ms |
5588 KB |
Output is correct |
87 |
Correct |
3 ms |
5076 KB |
Output is correct |
88 |
Correct |
4 ms |
5716 KB |
Output is correct |
89 |
Correct |
80 ms |
20172 KB |
Output is correct |
90 |
Correct |
64 ms |
17072 KB |
Output is correct |
91 |
Correct |
129 ms |
27896 KB |
Output is correct |
92 |
Correct |
3 ms |
5332 KB |
Output is correct |