#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = int;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define ln "\n"
struct directed_graph{
ll N;
vii edge, revedge;
vi par;
vii V;
directed_graph(vii E){
N = E.size();
edge.resize(N);
revedge.resize(N);
par.resize(N);
V.resize(N);
rep(i,0,N){
for(auto j: E[i]){
edge[i].pb(j);
revedge[j].pb(i);
}
}
}
vi ord;
vector<bool> flag;
void dfs1(ll now){
flag[now] = true;
for(auto next: edge[now]){
if(flag[next]) continue;
dfs1(next);
}
ord.pb(now);
}
void dfs2(ll p, ll now){
flag[now] = true;
par[now] = p;
for(auto next: revedge[now]){
if(flag[next]) continue;
dfs2(p, next);
}
}
void SCC(){
flag.resize(N);
rep(i,0,N){
if(!flag[i]) dfs1(i);
}
reverse(all(ord));
flag.assign(N,false);
for(auto el: ord){
if(!flag[el]){
dfs2(el,el);
}
}
rep(i,0,N) V[par[i]].pb(i);
}
};
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
vii edge(N), index(N);
rep(i,0,M){
edge[U[i]].pb(V[i]);
index[U[i]].pb(i);
}
directed_graph G(edge);
G.SCC();
ll good = -1;
vi ans;
{
std::queue<ll> que;
que.push(0);
vi flag(N);
vi rev(N,-1);
vi idx(N);
flag[0] = true;
rev[0] = 0;
while(!que.empty()){
ll now = que.front(); que.pop();
if(G.V[G.par[now]].size() >= 2 && edge[now].size() >= 2){
good = now;
while(now != 0){
ans.pb(idx[now]);
now = rev[now];
}
reverse(all(ans));
break;
}
rep(i,0,edge[now].size()){
ll next = edge[now][i];
if(flag[next]) continue;
flag[next] = true;
rev[next] = now;
idx[next] = index[now][i];
que.push(next);
}
}
}
if(good != -1){
std::set<ll> used;
for(auto el: ans){
used.insert(el);
used.insert(el^1);
}
std::queue<ll> que;
que.push(good);
vi rev(N,-1);
vi idx(N);
rev[good] = good;
while(!que.empty()){
ll now = que.front(); que.pop();
rep(i,0,edge[now].size()){
ll next = edge[now][i];
if(rev[next] != -1) continue;
if(used.count(index[now][i])) continue;
rev[next] = now;
idx[next] = index[now][i];
que.push(next);
}
}
rep(i,0,N){
if(rev[i] != -1){
vi ans2;
rep(j,0,edge[i].size()){
if(used.count(index[i][j])) continue;
ll next = edge[i][j];
if(next == good){
ans2.pb(index[i][j]);
break;
}
}
if(ans2.empty()) continue;
ll now = i;
while(now != good){
ans2.pb(idx[now]);
now = rev[now];
}
ll len = ans.size();
reverse(all(ans2));
for(auto el: ans2) ans.pb(el);
for(auto el: ans2) ans.pb(el^1);
reverse(all(ans2));
for(auto el: ans2) ans.pb(el);
for(auto el: ans2) ans.pb(el^1);
per(i,len-1,0) ans.pb(ans[i]);
return ans;
}
}
}
return false;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Partially correct |
0 ms |
212 KB |
Output is partially correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Partially correct |
1 ms |
212 KB |
Output is partially correct |
7 |
Partially correct |
30 ms |
8692 KB |
Output is partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
212 KB |
Output is partially correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Partially correct |
0 ms |
212 KB |
Output is partially correct |
4 |
Partially correct |
0 ms |
212 KB |
Output is partially correct |
5 |
Partially correct |
0 ms |
212 KB |
Output is partially correct |
6 |
Partially correct |
27 ms |
6932 KB |
Output is partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
2 ms |
596 KB |
Output is partially correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Partially correct |
0 ms |
212 KB |
Output is partially correct |
5 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
26 ms |
7484 KB |
Output is correct |
4 |
Correct |
28 ms |
7992 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
3 ms |
724 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
2 ms |
596 KB |
Output is correct |
15 |
Correct |
2 ms |
724 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
2 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
30 ms |
8404 KB |
Output is correct |
21 |
Correct |
30 ms |
7884 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
3 ms |
596 KB |
Output is correct |
27 |
Correct |
33 ms |
8476 KB |
Output is correct |
28 |
Correct |
34 ms |
8452 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
32 ms |
9164 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
42 ms |
8524 KB |
Output is correct |
33 |
Correct |
30 ms |
8060 KB |
Output is correct |
34 |
Correct |
17 ms |
4564 KB |
Output is correct |
35 |
Correct |
1 ms |
468 KB |
Output is correct |
36 |
Correct |
27 ms |
7068 KB |
Output is correct |
37 |
Correct |
30 ms |
8704 KB |
Output is correct |
38 |
Correct |
1 ms |
468 KB |
Output is correct |
39 |
Correct |
29 ms |
7108 KB |
Output is correct |
40 |
Correct |
1 ms |
596 KB |
Output is correct |
41 |
Correct |
34 ms |
9172 KB |
Output is correct |
42 |
Correct |
35 ms |
8572 KB |
Output is correct |
43 |
Correct |
1 ms |
212 KB |
Output is correct |
44 |
Correct |
2 ms |
596 KB |
Output is correct |
45 |
Correct |
1 ms |
596 KB |
Output is correct |
46 |
Correct |
14 ms |
4136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Partially correct |
0 ms |
212 KB |
Output is partially correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Partially correct |
1 ms |
212 KB |
Output is partially correct |
7 |
Partially correct |
30 ms |
8692 KB |
Output is partially correct |
8 |
Partially correct |
1 ms |
212 KB |
Output is partially correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Partially correct |
0 ms |
212 KB |
Output is partially correct |
11 |
Partially correct |
0 ms |
212 KB |
Output is partially correct |
12 |
Partially correct |
0 ms |
212 KB |
Output is partially correct |
13 |
Partially correct |
27 ms |
6932 KB |
Output is partially correct |
14 |
Partially correct |
2 ms |
596 KB |
Output is partially correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Partially correct |
0 ms |
212 KB |
Output is partially correct |
18 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |