#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define sz(x) int(x.size())
const int mx = 100'000;
vpii edge[mx];
vpii revedge[mx];
int N, M;
queue<int> tbv;
int src = 0;
vi pushed(mx, 0);
vi killed(mx, 0);
vi outdeg(mx, 0);
vi incedge(mx, -1);
void addvec(vi& a, vi& b)
{
for(int u : b)
a.push_back(u);
}
void rev(vi& a)
{
reverse(a.begin(), a.end());
}
void addrev(vi& a, vi& b)
{
rev(b);
addvec(a, b);
rev(b);
}
vi nodevis(mx, 0);
vi cyclic(mx, 0);
bool samecycle = 0;
vi lst1, nodelst1, cyc1, nodecyc1;
int bannededge;
void dfs1(int u)
{
for(pii vp : edge[u])
{
int v = vp.first;
if(killed[v])
continue;
if(nodevis[v] == 0)
{
lst1.push_back(vp.second);
nodelst1.push_back(vp.first);
if(u == src)
bannededge = vp.second;
nodevis[v] = 1;
dfs1(v);
}
else if(nodevis[v] == 1)
{
// samecycle = 1;
nodecyc1.push_back(v);
cyclic[v] = 1;
cyc1.push_back(vp.second);
while(1)
{
if(nodelst1.back() == v)
break;
nodecyc1.push_back(nodelst1.back());
cyclic[nodelst1.back()] = 1;
cyc1.push_back(lst1.back());
nodelst1.pop_back();
lst1.pop_back();
}
rev(nodecyc1);
rev(cyc1);
}
return;
}
}
vi lst2, cyc2, nodelst2, nodecyc2;
void dfs2(int u)
{
for(pii vp : edge[u])
{
if(vp.second == bannededge)
continue;
int v = vp.first;
if(killed[v])
continue;
if(nodevis[v] == 0)
{
lst2.push_back(vp.second);
nodelst2.push_back(vp.first);
if(u == src)
bannededge = vp.second;
nodevis[v] = 2;
dfs2(v);
}
else if(nodevis[v] == 2)
{
nodecyc2.push_back(v);
cyc2.push_back(vp.second);
while(1)
{
if(nodelst2.back() == v)
break;
nodecyc2.push_back(nodelst2.back());
cyc2.push_back(lst2.back());
nodelst2.pop_back();
lst2.pop_back();
}
rev(nodecyc2);
rev(cyc2);
}
else if(nodevis[v] == 1 && !cyclic[v])
{
samecycle = 1;
nodecyc2 = nodecyc1;
cyc2 = cyc1;
// cerr << "no"
int id = 0;
while(nodelst1[id] != v)
id++;
nodelst2.push_back(v);
lst2.push_back(vp.second);
for(id++; id < sz(nodelst1); id++)
{
nodelst2.push_back(nodelst1[id]);
lst2.push_back(lst1[id-1]);
}
}
else if(nodevis[v] == 1 && cyclic[v])
{
samecycle = 1;
lst2.push_back(vp.second);
int z = 0;
while(nodecyc1[z] != v)
z++;
for(int f = z+1; f < sz(cyc1); f++)
{
cyc2.push_back(cyc1[f]);
nodecyc2.push_back(nodecyc1[f]);
}
for(int f = 0; f <= z; f++)
{
cyc2.push_back(cyc1[f]);
nodecyc2.push_back(nodecyc1[f]);
}
}
return;
}
}
variant<bool, vi> find_journey(int N_, int M_, vi U, vi V)
{
N = N_;
M = M_;
for(int j = 0; j < M; j++)
{
edge[U[j]].push_back({V[j], j});
revedge[V[j]].push_back({U[j], j});
outdeg[U[j]]++;
}
for(int i = 0; i < N; i++)
{
if(outdeg[i] == 0)
{
pushed[i] = 1;
tbv.push(i);
}
}
if(pushed[src])
{
return false;
}
vi originlist;
while(1)
{
if(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
killed[u] = 1;
for(pii vp : revedge[u])
{
int v = vp.first;
outdeg[v]--;
if(outdeg[v] == 0)
{
pushed[v] = 1;
if(v == src)
{
// gettime();
return false;
}
tbv.push(v);
}
}
}
else if(outdeg[src] == 1)
{
int newsrc;
for(pii vp : edge[src])
{
if(!pushed[vp.first])
{
newsrc = vp.first;
incedge[newsrc] = vp.second;
originlist.push_back(vp.second);
break;
}
}
pushed[src] = 1;
killed[src] = 1;
for(pii vp : revedge[src])
{
int v = vp.first;
if(vp.second == incedge[src])
continue;
outdeg[v]--;
if(outdeg[v] == 0)
{
pushed[v] = 1;
if(pushed[newsrc])
return false;
tbv.push(v);
}
}
src = newsrc;
}
else
{
break;
}
}
nodevis[src] = 1;
nodelst1.push_back(src);
dfs1(src);
nodelst2.push_back(src);
dfs2(src);
vi res;
if(!samecycle)
{
addvec(res, originlist);
addvec(res, lst1);
addvec(res, cyc1);
addrev(res, lst1);
addvec(res, lst2);
addvec(res, cyc2);
addrev(res, lst2);
addvec(res, lst1);
addrev(res, cyc1);
addrev(res, lst1);
addvec(res, lst2);
addrev(res, cyc2);
addrev(res, lst2);
addrev(res, originlist);
}
else
{
addvec(res, originlist);
addvec(res, lst1);
addvec(res, cyc1);
addrev(res, lst1);
addvec(res, lst2);
addrev(res, cyc2);
addrev(res, lst2);
addrev(res, originlist);
}
return res;
}
Compilation message
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, vi, vi)':
islands.cpp:284:8: warning: 'newsrc' may be used uninitialized in this function [-Wmaybe-uninitialized]
284 | src = newsrc;
| ~~~~^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
Output is correct |
2 |
Correct |
4 ms |
7252 KB |
Output is correct |
3 |
Correct |
4 ms |
7336 KB |
Output is correct |
4 |
Correct |
5 ms |
7252 KB |
Output is correct |
5 |
Correct |
4 ms |
7252 KB |
Output is correct |
6 |
Correct |
4 ms |
7252 KB |
Output is correct |
7 |
Correct |
43 ms |
13648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
Output is correct |
2 |
Correct |
4 ms |
7252 KB |
Output is correct |
3 |
Correct |
4 ms |
7252 KB |
Output is correct |
4 |
Correct |
6 ms |
7280 KB |
Output is correct |
5 |
Correct |
4 ms |
7252 KB |
Output is correct |
6 |
Correct |
38 ms |
13332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7508 KB |
Output is correct |
2 |
Correct |
5 ms |
7252 KB |
Output is correct |
3 |
Correct |
4 ms |
7268 KB |
Output is correct |
4 |
Correct |
4 ms |
7252 KB |
Output is correct |
5 |
Correct |
5 ms |
7380 KB |
Output is correct |
6 |
Correct |
5 ms |
7252 KB |
Output is correct |
7 |
Correct |
6 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7280 KB |
Output is correct |
9 |
Correct |
4 ms |
7380 KB |
Output is correct |
10 |
Correct |
5 ms |
7380 KB |
Output is correct |
11 |
Correct |
4 ms |
7352 KB |
Output is correct |
12 |
Correct |
5 ms |
7380 KB |
Output is correct |
13 |
Correct |
4 ms |
7252 KB |
Output is correct |
14 |
Correct |
4 ms |
7252 KB |
Output is correct |
15 |
Correct |
4 ms |
7252 KB |
Output is correct |
16 |
Correct |
4 ms |
7252 KB |
Output is correct |
17 |
Correct |
28 ms |
11176 KB |
Output is correct |
18 |
Correct |
22 ms |
10836 KB |
Output is correct |
19 |
Correct |
4 ms |
7252 KB |
Output is correct |
20 |
Correct |
4 ms |
7252 KB |
Output is correct |
21 |
Correct |
5 ms |
7252 KB |
Output is correct |
22 |
Correct |
4 ms |
7252 KB |
Output is correct |
23 |
Correct |
40 ms |
13260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7252 KB |
Output is correct |
2 |
Correct |
5 ms |
7508 KB |
Output is correct |
3 |
Correct |
40 ms |
13772 KB |
Output is correct |
4 |
Correct |
56 ms |
14388 KB |
Output is correct |
5 |
Correct |
5 ms |
7508 KB |
Output is correct |
6 |
Correct |
5 ms |
7508 KB |
Output is correct |
7 |
Correct |
4 ms |
7252 KB |
Output is correct |
8 |
Correct |
4 ms |
7252 KB |
Output is correct |
9 |
Correct |
4 ms |
7252 KB |
Output is correct |
10 |
Correct |
5 ms |
7508 KB |
Output is correct |
11 |
Correct |
7 ms |
7508 KB |
Output is correct |
12 |
Correct |
5 ms |
7496 KB |
Output is correct |
13 |
Correct |
6 ms |
7636 KB |
Output is correct |
14 |
Correct |
6 ms |
7528 KB |
Output is correct |
15 |
Correct |
5 ms |
7508 KB |
Output is correct |
16 |
Correct |
5 ms |
7380 KB |
Output is correct |
17 |
Correct |
5 ms |
7252 KB |
Output is correct |
18 |
Correct |
5 ms |
7508 KB |
Output is correct |
19 |
Correct |
4 ms |
7380 KB |
Output is correct |
20 |
Correct |
42 ms |
15052 KB |
Output is correct |
21 |
Correct |
42 ms |
14540 KB |
Output is correct |
22 |
Correct |
5 ms |
7380 KB |
Output is correct |
23 |
Correct |
4 ms |
7380 KB |
Output is correct |
24 |
Correct |
4 ms |
7380 KB |
Output is correct |
25 |
Correct |
5 ms |
7380 KB |
Output is correct |
26 |
Correct |
5 ms |
7544 KB |
Output is correct |
27 |
Correct |
45 ms |
14660 KB |
Output is correct |
28 |
Correct |
43 ms |
14732 KB |
Output is correct |
29 |
Correct |
4 ms |
7252 KB |
Output is correct |
30 |
Correct |
48 ms |
15824 KB |
Output is correct |
31 |
Correct |
4 ms |
7252 KB |
Output is correct |
32 |
Correct |
45 ms |
14784 KB |
Output is correct |
33 |
Correct |
46 ms |
14468 KB |
Output is correct |
34 |
Correct |
25 ms |
11152 KB |
Output is correct |
35 |
Correct |
5 ms |
7380 KB |
Output is correct |
36 |
Correct |
38 ms |
13796 KB |
Output is correct |
37 |
Correct |
44 ms |
15456 KB |
Output is correct |
38 |
Correct |
5 ms |
7380 KB |
Output is correct |
39 |
Correct |
38 ms |
13940 KB |
Output is correct |
40 |
Correct |
7 ms |
7380 KB |
Output is correct |
41 |
Correct |
50 ms |
15836 KB |
Output is correct |
42 |
Correct |
42 ms |
14864 KB |
Output is correct |
43 |
Correct |
4 ms |
7252 KB |
Output is correct |
44 |
Correct |
5 ms |
7508 KB |
Output is correct |
45 |
Correct |
5 ms |
7508 KB |
Output is correct |
46 |
Correct |
22 ms |
10688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
Output is correct |
2 |
Correct |
4 ms |
7252 KB |
Output is correct |
3 |
Correct |
4 ms |
7336 KB |
Output is correct |
4 |
Correct |
5 ms |
7252 KB |
Output is correct |
5 |
Correct |
4 ms |
7252 KB |
Output is correct |
6 |
Correct |
4 ms |
7252 KB |
Output is correct |
7 |
Correct |
43 ms |
13648 KB |
Output is correct |
8 |
Correct |
4 ms |
7252 KB |
Output is correct |
9 |
Correct |
4 ms |
7252 KB |
Output is correct |
10 |
Correct |
4 ms |
7252 KB |
Output is correct |
11 |
Correct |
6 ms |
7280 KB |
Output is correct |
12 |
Correct |
4 ms |
7252 KB |
Output is correct |
13 |
Correct |
38 ms |
13332 KB |
Output is correct |
14 |
Correct |
5 ms |
7508 KB |
Output is correct |
15 |
Correct |
5 ms |
7252 KB |
Output is correct |
16 |
Correct |
4 ms |
7268 KB |
Output is correct |
17 |
Correct |
4 ms |
7252 KB |
Output is correct |
18 |
Correct |
5 ms |
7380 KB |
Output is correct |
19 |
Correct |
5 ms |
7252 KB |
Output is correct |
20 |
Correct |
6 ms |
7380 KB |
Output is correct |
21 |
Correct |
4 ms |
7280 KB |
Output is correct |
22 |
Correct |
4 ms |
7380 KB |
Output is correct |
23 |
Correct |
5 ms |
7380 KB |
Output is correct |
24 |
Correct |
4 ms |
7352 KB |
Output is correct |
25 |
Correct |
5 ms |
7380 KB |
Output is correct |
26 |
Correct |
4 ms |
7252 KB |
Output is correct |
27 |
Correct |
4 ms |
7252 KB |
Output is correct |
28 |
Correct |
4 ms |
7252 KB |
Output is correct |
29 |
Correct |
4 ms |
7252 KB |
Output is correct |
30 |
Correct |
28 ms |
11176 KB |
Output is correct |
31 |
Correct |
22 ms |
10836 KB |
Output is correct |
32 |
Correct |
4 ms |
7252 KB |
Output is correct |
33 |
Correct |
4 ms |
7252 KB |
Output is correct |
34 |
Correct |
5 ms |
7252 KB |
Output is correct |
35 |
Correct |
4 ms |
7252 KB |
Output is correct |
36 |
Correct |
40 ms |
13260 KB |
Output is correct |
37 |
Correct |
4 ms |
7252 KB |
Output is correct |
38 |
Correct |
4 ms |
7252 KB |
Output is correct |
39 |
Correct |
4 ms |
7380 KB |
Output is correct |
40 |
Correct |
4 ms |
7380 KB |
Output is correct |
41 |
Correct |
22 ms |
10636 KB |
Output is correct |
42 |
Correct |
7 ms |
7532 KB |
Output is correct |
43 |
Correct |
49 ms |
12432 KB |
Output is correct |
44 |
Correct |
49 ms |
12360 KB |
Output is correct |
45 |
Correct |
60 ms |
12380 KB |
Output is correct |
46 |
Correct |
4 ms |
7264 KB |
Output is correct |
47 |
Correct |
4 ms |
7252 KB |
Output is correct |
48 |
Correct |
4 ms |
7252 KB |
Output is correct |
49 |
Correct |
5 ms |
7508 KB |
Output is correct |
50 |
Correct |
123 ms |
21544 KB |
Output is correct |
51 |
Correct |
118 ms |
17532 KB |
Output is correct |
52 |
Correct |
97 ms |
17484 KB |
Output is correct |
53 |
Correct |
95 ms |
17480 KB |
Output is correct |
54 |
Correct |
106 ms |
17500 KB |
Output is correct |
55 |
Correct |
117 ms |
17480 KB |
Output is correct |
56 |
Correct |
98 ms |
17488 KB |
Output is correct |
57 |
Correct |
68 ms |
15904 KB |
Output is correct |
58 |
Correct |
108 ms |
21712 KB |
Output is correct |
59 |
Correct |
109 ms |
17508 KB |
Output is correct |
60 |
Correct |
96 ms |
16972 KB |
Output is correct |
61 |
Correct |
98 ms |
17248 KB |
Output is correct |
62 |
Correct |
22 ms |
9372 KB |
Output is correct |
63 |
Correct |
89 ms |
17028 KB |
Output is correct |
64 |
Correct |
28 ms |
11596 KB |
Output is correct |
65 |
Correct |
4 ms |
7252 KB |
Output is correct |
66 |
Correct |
5 ms |
7380 KB |
Output is correct |
67 |
Correct |
141 ms |
17496 KB |
Output is correct |
68 |
Correct |
54 ms |
15820 KB |
Output is correct |
69 |
Correct |
73 ms |
13364 KB |
Output is correct |
70 |
Correct |
5 ms |
7508 KB |
Output is correct |
71 |
Correct |
82 ms |
14424 KB |
Output is correct |
72 |
Correct |
4 ms |
7252 KB |
Output is correct |
73 |
Correct |
85 ms |
16852 KB |
Output is correct |
74 |
Correct |
106 ms |
21872 KB |
Output is correct |
75 |
Correct |
8 ms |
7764 KB |
Output is correct |
76 |
Correct |
52 ms |
13968 KB |
Output is correct |
77 |
Correct |
66 ms |
15208 KB |
Output is correct |
78 |
Correct |
131 ms |
17236 KB |
Output is correct |
79 |
Correct |
4 ms |
7252 KB |
Output is correct |
80 |
Correct |
126 ms |
21420 KB |
Output is correct |
81 |
Correct |
5 ms |
7508 KB |
Output is correct |
82 |
Correct |
41 ms |
14268 KB |
Output is correct |
83 |
Correct |
5 ms |
7380 KB |
Output is correct |
84 |
Correct |
6 ms |
7252 KB |
Output is correct |
85 |
Correct |
45 ms |
14640 KB |
Output is correct |
86 |
Correct |
5 ms |
7380 KB |
Output is correct |
87 |
Correct |
7 ms |
7764 KB |
Output is correct |
88 |
Correct |
7 ms |
7508 KB |
Output is correct |
89 |
Correct |
106 ms |
16984 KB |
Output is correct |
90 |
Correct |
102 ms |
17264 KB |
Output is correct |
91 |
Correct |
118 ms |
21812 KB |
Output is correct |
92 |
Correct |
4 ms |
7252 KB |
Output is correct |