#include <bits/stdc++.h>
using namespace std;
int dg[100009];
vector<int>to[100009],frm[100009];
int ed[200009][2];
bool incy[200009],vsnd[200009],dl[200009];
vector<int>tocy[2],cy[2];
bool fnd;
void dfs(int x,int u)
{
//cout<<x<<" "<<tocy[u].back()<<" "<<u<<endl;
if(fnd||(vsnd[x]==2))return;
if(vsnd[x]==1)
{
fnd=true;
while(ed[tocy[u].back()][0]!=x){cy[u].push_back(tocy[u].back());tocy[u].pop_back();}
cy[u].push_back(tocy[u].back());tocy[u].pop_back();
reverse(cy[u].begin(),cy[u].end());
return;
}
vsnd[x]=1;
for(auto v:frm[x])
{if(!dl[ed[v][1]]){tocy[u].push_back(v);dfs(ed[v][1],u);if(fnd)return ;tocy[u].pop_back();}}
vsnd[x]=2;
}
variant<bool,vector<int> > find_journey(int N, int M, vector<int> U, vector<int> V)
{
for(int i=0;i<M;i++)
{
ed[i][0]=U[i];
ed[i][1]=V[i];
frm[U[i]].push_back(i);
to[V[i]].push_back(i);
dg[U[i]]++;
}
queue<int>qq;
for(int i=0;i<N;i++)
if(dg[i]==0)qq.push(i);
while(!qq.empty())
{
int u=qq.front();
qq.pop();
dl[u]=1;
for(auto v:to[u])
{
dg[ed[v][0]]--;
if(dg[ed[v][0]]==0)qq.push(ed[v][0]);
}
}
if(dl[0])return false;
int h=0,u=-1,v=-1;
vector<int>gg;
while(true)
{
vector<int>bb;
for(auto w:frm[h])
if((!dl[ed[w][1]]))bb.push_back(w);
if(bb.empty())return false;
if(bb.size()==1)
{ qq.push(h);
while(!qq.empty())
{
int uu=qq.front();
qq.pop();
dl[uu]=1;
for(auto vv:to[uu])
{
dg[ed[vv][0]]--;
if((!dl[ed[vv][0]])&&dg[ed[vv][0]]==0)qq.push(ed[vv][0]);
}
}
gg.push_back(bb[0]);
h=ed[bb[0]][1];
if(dl[h])return false;
continue;
}
u=bb[0],v=bb[1];
break;
}
dl[h]=0;
vsnd[h]=1;
tocy[0].push_back(u);
fnd=false;
dfs(ed[u][1],0);
memset(vsnd,0,sizeof vsnd);
fnd=false;
vsnd[h]=1;
tocy[1].push_back(v);
dfs(ed[v][1],1);
/*cout<<h<<' '<<u<<" "<<v<<" "<<ed[u][1]<<" "<<ed[v][1]<<endl;
cout<<"to ";
for(auto w:gg)cout<<w<<" ";
cout<<endl;
cout<<"tocy0 ";
for(auto w:tocy[0])cout<<w<<" ";
cout<<endl;
cout<<"cy0 ";
for(auto w:cy[0])cout<<w<<" ";
cout<<endl;
cout<<"tocy1 ";
for(auto w:tocy[1])cout<<w<<" ";
cout<<endl;
cout<<"cy1 ";
for(auto w:cy[1])cout<<w<<" ";
cout<<endl;
// return {-1};*/
// if((cy[0].empty())||(cy[1].empty()))return false;
vector<int>ans=gg;
for(auto w:tocy[0])ans.push_back(w);
for(auto w:cy[0]){ans.push_back(w);incy[w]=1;}
reverse(tocy[0].begin(),tocy[0].end());
for(auto w:tocy[0])ans.push_back(w);
reverse(tocy[0].begin(),tocy[0].end());
int rr=-1;
vector<int>f;
for(auto w:tocy[1])
{
if(incy[w]){rr=w;break;}
f.push_back(w);
}
if(rr==-1)
{
for(auto w:cy[1])
{
if(incy[w]){rr=w;break;}
f.push_back(w);
}
}
if(rr==-1)
{
for(auto w:tocy[1]) ans.push_back(w);
for(auto w:cy[1])ans.push_back(w);
reverse(tocy[1].begin(),tocy[1].end());
for(auto w:tocy[1])ans.push_back(w);
reverse(tocy[1].begin(),tocy[1].end());
for(auto w:tocy[0])ans.push_back(w);
reverse(cy[0].begin(),cy[0].end());
for(auto w:cy[0])ans.push_back(w);
reverse(tocy[0].begin(),tocy[0].end());
for(auto w:tocy[0])ans.push_back(w);
for(auto w:tocy[1])ans.push_back(w);
reverse(cy[1].begin(),cy[1].end());
for(auto w:cy[1])ans.push_back(w);
reverse(tocy[1].begin(),tocy[1].end());
for(auto w:tocy[1])ans.push_back(w);
reverse(tocy[1].begin(),tocy[1].end());
reverse(gg.begin(),gg.end());
for(auto w:gg)ans.push_back(w);
return ans;
}
for(auto w:f)ans.push_back(w);
for(int i=0;i<cy[0].size();i++)
{
if(cy[0][i]!=rr)continue;
for(int j=i-1;j>=0;j--)ans.push_back(cy[0][j]);
for(int j=cy[0].size()-1;j>=i;j--)ans.push_back(cy[0][j]);
reverse(f.begin(),f.end());
for(auto w:f)ans.push_back(w);
reverse(gg.begin(),gg.end());
for(auto w:gg)ans.push_back(w);
return ans;
}
}
Compilation message
islands.cpp: In function 'void dfs(int, int)':
islands.cpp:12:21: warning: comparison of constant '2' with boolean expression is always false [-Wbool-compare]
12 | if(fnd||(vsnd[x]==2))return;
| ~~~~~~~^~~
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:159:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for(int i=0;i<cy[0].size();i++)
| ~^~~~~~~~~~~~~
islands.cpp:37:15: warning: control reaches end of non-void function [-Wreturn-type]
37 | queue<int>qq;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
5204 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
5204 KB |
Output is correct |
7 |
Correct |
29 ms |
12000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5204 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
5204 KB |
Output is correct |
4 |
Correct |
2 ms |
5204 KB |
Output is correct |
5 |
Correct |
3 ms |
5204 KB |
Output is correct |
6 |
Correct |
26 ms |
10744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5332 KB |
Output is correct |
2 |
Correct |
2 ms |
5008 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
5204 KB |
Output is correct |
5 |
Correct |
3 ms |
5076 KB |
Output is correct |
6 |
Correct |
2 ms |
5204 KB |
Output is correct |
7 |
Correct |
2 ms |
5076 KB |
Output is correct |
8 |
Correct |
3 ms |
5204 KB |
Output is correct |
9 |
Correct |
2 ms |
5204 KB |
Output is correct |
10 |
Correct |
3 ms |
5332 KB |
Output is correct |
11 |
Correct |
2 ms |
5204 KB |
Output is correct |
12 |
Correct |
3 ms |
5332 KB |
Output is correct |
13 |
Correct |
2 ms |
4948 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
2 ms |
5204 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
18 ms |
8660 KB |
Output is correct |
18 |
Correct |
16 ms |
8212 KB |
Output is correct |
19 |
Correct |
2 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
5204 KB |
Output is correct |
21 |
Correct |
2 ms |
5204 KB |
Output is correct |
22 |
Correct |
2 ms |
5204 KB |
Output is correct |
23 |
Correct |
26 ms |
10732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5204 KB |
Output is correct |
2 |
Correct |
4 ms |
5332 KB |
Output is correct |
3 |
Correct |
26 ms |
11272 KB |
Output is correct |
4 |
Correct |
28 ms |
11448 KB |
Output is correct |
5 |
Correct |
3 ms |
5332 KB |
Output is correct |
6 |
Correct |
3 ms |
5332 KB |
Output is correct |
7 |
Correct |
2 ms |
5204 KB |
Output is correct |
8 |
Correct |
2 ms |
5204 KB |
Output is correct |
9 |
Correct |
2 ms |
5204 KB |
Output is correct |
10 |
Correct |
3 ms |
5460 KB |
Output is correct |
11 |
Correct |
3 ms |
5076 KB |
Output is correct |
12 |
Correct |
3 ms |
5332 KB |
Output is correct |
13 |
Correct |
3 ms |
5460 KB |
Output is correct |
14 |
Correct |
3 ms |
5332 KB |
Output is correct |
15 |
Correct |
4 ms |
5332 KB |
Output is correct |
16 |
Correct |
3 ms |
5332 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5332 KB |
Output is correct |
19 |
Correct |
3 ms |
5204 KB |
Output is correct |
20 |
Correct |
30 ms |
12080 KB |
Output is correct |
21 |
Correct |
29 ms |
11672 KB |
Output is correct |
22 |
Correct |
3 ms |
5076 KB |
Output is correct |
23 |
Correct |
3 ms |
4948 KB |
Output is correct |
24 |
Correct |
2 ms |
4948 KB |
Output is correct |
25 |
Correct |
3 ms |
5204 KB |
Output is correct |
26 |
Correct |
3 ms |
5460 KB |
Output is correct |
27 |
Correct |
39 ms |
11856 KB |
Output is correct |
28 |
Correct |
29 ms |
12008 KB |
Output is correct |
29 |
Correct |
2 ms |
4948 KB |
Output is correct |
30 |
Correct |
31 ms |
12472 KB |
Output is correct |
31 |
Correct |
2 ms |
5204 KB |
Output is correct |
32 |
Correct |
28 ms |
11928 KB |
Output is correct |
33 |
Correct |
27 ms |
11860 KB |
Output is correct |
34 |
Correct |
17 ms |
8660 KB |
Output is correct |
35 |
Correct |
3 ms |
5332 KB |
Output is correct |
36 |
Correct |
26 ms |
10988 KB |
Output is correct |
37 |
Correct |
30 ms |
12260 KB |
Output is correct |
38 |
Correct |
3 ms |
5004 KB |
Output is correct |
39 |
Correct |
24 ms |
10708 KB |
Output is correct |
40 |
Correct |
3 ms |
5332 KB |
Output is correct |
41 |
Correct |
31 ms |
12424 KB |
Output is correct |
42 |
Correct |
29 ms |
12012 KB |
Output is correct |
43 |
Correct |
2 ms |
4948 KB |
Output is correct |
44 |
Correct |
3 ms |
5140 KB |
Output is correct |
45 |
Correct |
3 ms |
5456 KB |
Output is correct |
46 |
Correct |
17 ms |
8212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
5204 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
5204 KB |
Output is correct |
7 |
Correct |
29 ms |
12000 KB |
Output is correct |
8 |
Correct |
2 ms |
5204 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
5204 KB |
Output is correct |
11 |
Correct |
2 ms |
5204 KB |
Output is correct |
12 |
Correct |
3 ms |
5204 KB |
Output is correct |
13 |
Correct |
26 ms |
10744 KB |
Output is correct |
14 |
Correct |
4 ms |
5332 KB |
Output is correct |
15 |
Correct |
2 ms |
5008 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
2 ms |
5204 KB |
Output is correct |
18 |
Correct |
3 ms |
5076 KB |
Output is correct |
19 |
Correct |
2 ms |
5204 KB |
Output is correct |
20 |
Correct |
2 ms |
5076 KB |
Output is correct |
21 |
Correct |
3 ms |
5204 KB |
Output is correct |
22 |
Correct |
2 ms |
5204 KB |
Output is correct |
23 |
Correct |
3 ms |
5332 KB |
Output is correct |
24 |
Correct |
2 ms |
5204 KB |
Output is correct |
25 |
Correct |
3 ms |
5332 KB |
Output is correct |
26 |
Correct |
2 ms |
4948 KB |
Output is correct |
27 |
Correct |
2 ms |
4948 KB |
Output is correct |
28 |
Correct |
2 ms |
5204 KB |
Output is correct |
29 |
Correct |
3 ms |
4948 KB |
Output is correct |
30 |
Correct |
18 ms |
8660 KB |
Output is correct |
31 |
Correct |
16 ms |
8212 KB |
Output is correct |
32 |
Correct |
2 ms |
4948 KB |
Output is correct |
33 |
Correct |
3 ms |
5204 KB |
Output is correct |
34 |
Correct |
2 ms |
5204 KB |
Output is correct |
35 |
Correct |
2 ms |
5204 KB |
Output is correct |
36 |
Correct |
26 ms |
10732 KB |
Output is correct |
37 |
Correct |
2 ms |
5204 KB |
Output is correct |
38 |
Correct |
2 ms |
4948 KB |
Output is correct |
39 |
Correct |
2 ms |
4948 KB |
Output is correct |
40 |
Correct |
2 ms |
4948 KB |
Output is correct |
41 |
Correct |
15 ms |
8156 KB |
Output is correct |
42 |
Correct |
3 ms |
5204 KB |
Output is correct |
43 |
Correct |
27 ms |
10916 KB |
Output is correct |
44 |
Correct |
27 ms |
12052 KB |
Output is correct |
45 |
Correct |
29 ms |
12232 KB |
Output is correct |
46 |
Correct |
2 ms |
5204 KB |
Output is correct |
47 |
Correct |
2 ms |
5204 KB |
Output is correct |
48 |
Correct |
3 ms |
5204 KB |
Output is correct |
49 |
Correct |
3 ms |
5400 KB |
Output is correct |
50 |
Correct |
94 ms |
23160 KB |
Output is correct |
51 |
Correct |
77 ms |
18764 KB |
Output is correct |
52 |
Correct |
68 ms |
18720 KB |
Output is correct |
53 |
Correct |
77 ms |
19100 KB |
Output is correct |
54 |
Correct |
62 ms |
19144 KB |
Output is correct |
55 |
Correct |
62 ms |
19080 KB |
Output is correct |
56 |
Correct |
64 ms |
19252 KB |
Output is correct |
57 |
Correct |
56 ms |
17420 KB |
Output is correct |
58 |
Correct |
78 ms |
21572 KB |
Output is correct |
59 |
Correct |
61 ms |
18220 KB |
Output is correct |
60 |
Correct |
62 ms |
17520 KB |
Output is correct |
61 |
Correct |
84 ms |
17568 KB |
Output is correct |
62 |
Correct |
14 ms |
7824 KB |
Output is correct |
63 |
Correct |
61 ms |
17612 KB |
Output is correct |
64 |
Correct |
19 ms |
9940 KB |
Output is correct |
65 |
Correct |
2 ms |
5204 KB |
Output is correct |
66 |
Correct |
3 ms |
5204 KB |
Output is correct |
67 |
Correct |
106 ms |
18348 KB |
Output is correct |
68 |
Correct |
35 ms |
13980 KB |
Output is correct |
69 |
Correct |
54 ms |
13208 KB |
Output is correct |
70 |
Correct |
3 ms |
5460 KB |
Output is correct |
71 |
Correct |
43 ms |
13776 KB |
Output is correct |
72 |
Correct |
2 ms |
5204 KB |
Output is correct |
73 |
Correct |
52 ms |
16972 KB |
Output is correct |
74 |
Correct |
90 ms |
25724 KB |
Output is correct |
75 |
Correct |
7 ms |
5716 KB |
Output is correct |
76 |
Correct |
33 ms |
13816 KB |
Output is correct |
77 |
Correct |
53 ms |
15224 KB |
Output is correct |
78 |
Correct |
71 ms |
17560 KB |
Output is correct |
79 |
Correct |
3 ms |
5204 KB |
Output is correct |
80 |
Correct |
109 ms |
24584 KB |
Output is correct |
81 |
Correct |
3 ms |
5332 KB |
Output is correct |
82 |
Correct |
30 ms |
12400 KB |
Output is correct |
83 |
Correct |
3 ms |
5204 KB |
Output is correct |
84 |
Correct |
3 ms |
5204 KB |
Output is correct |
85 |
Correct |
33 ms |
13456 KB |
Output is correct |
86 |
Correct |
3 ms |
5332 KB |
Output is correct |
87 |
Correct |
3 ms |
5844 KB |
Output is correct |
88 |
Correct |
4 ms |
5412 KB |
Output is correct |
89 |
Correct |
70 ms |
17568 KB |
Output is correct |
90 |
Correct |
75 ms |
17688 KB |
Output is correct |
91 |
Correct |
115 ms |
23844 KB |
Output is correct |
92 |
Correct |
3 ms |
5204 KB |
Output is correct |