#include "islands.h"
#define here cerr<<"=======================\n"
#include <iostream>
#include <vector>
#include <variant>
#include <algorithm>
#include <set>
#define dbg(x) cerr<<#x<<": "<<x<<endl
#define ll int
#define pll pair<ll,ll>
#define pb push_back
#define popb pop_back
#define all(x_) x_.begin(), x_.end()
using namespace std;
#define maxn 1005
ll n,m;
vector<ll> g[maxn];
ll id[maxn][maxn];
vector<ll> allid[maxn][maxn];
set<pll> sss;
vector<ll> gen(vector<ll> v){
vector<ll> ans;
for(ll i = 0;i<=v.size()/2-1;i++) ans.pb(v[i]);
for(ll i = v.size()-1;i>=v.size()/2;i--) ans.pb(v[i]);
for(ll i = v.size()/2 - 1;i>=0;i--) ans.pb(v[i]);
for(ll i = v.size()/2;i<=v.size()-1;i++) ans.pb(v[i]);
return ans;
}
bool vis[maxn];
bool naso = 0;
ll x,y,tip;
vector<ll> cur;
void dfs1(ll u,ll p){
vis[u] = 1;
cur.pb(u);
if(g[u].size()-(u!=p)>1){
naso = 1;
tip = 1;
x = u;
y = p;
return;
}
for(ll s : g[u]){
if(s==p) continue;
if(vis[s]) continue;
if(allid[u][s].size()>1){
naso = 1;
tip = 2;
x = u;
y = s;
return;
}
dfs1(s,u);
if(naso) return;
}
cur.popb();
}
bool sub = 1;
vector<ll> cyc;
ll in[maxn];
ll ti = 0;
void dfs2(ll u,ll p){
vis[u] = 1;
in[u] = 1;
cur.pb(u);
for(ll s : g[u]){
if(vis[s]&&in[s]){
while(cur.size()){
cyc.pb(cur.back());
if(cyc.back()==s) break;
cur.popb();
}
naso = 1;
return;
}
if(vis[s]) continue;
dfs2(s,u);
if(naso) return;
}
in[u] = 0;
cur.popb();
}
void dfs3(ll u,ll p,ll en){
cur.pb(u);
if(u==en){
naso = 1;
return;
}
vis[u] = 1;
for(ll s : g[u]){
if(vis[s]) continue;
dfs3(s,u,en);
if(naso) return;
}
if(cur.size()) cur.popb();
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
n = N;
m = M;
for(ll &x : U) x++;
for(ll &x : V) x++;
if(sub&&n==2){
vector<vector<ll> > cnt(3);
for(ll i = 0;i<m;i++){
ll x = U[i],y = V[i];
cnt[x].pb(i);
}
bool ok = cnt[1].size()>=2&&cnt[2].size()>=1;
if(!ok) return ok;
ll x = cnt[1][0],y = cnt[1][1];
ll z = cnt[2][0];
vector<ll> ans;
ans.pb(x);
ans.pb(z);
ans.pb(y);
ans.pb(x);
ans.pb(z);
ans.pb(y);
return ans;
}
for(ll i = 1;i<=n;i++) for(ll j = 1;j<=n;j++) id[i][j] = -1;
for(ll i = 0;i<m;i++){
ll x = U[i],y = V[i];
if(id[x][y]==-1) g[x].pb(y);
id[x][y] = i;
allid[x][y].pb(i);
sss.insert({x,y});
}
if(sub&&n<=400&&sss.size()==n*(n-1)&&m==n*(n-1)){
ll x = id[1][2];
ll y = id[2][3];
ll z = id[3][1];
ll rx = id[2][1];
ll ry = id[3][2];
ll rz = id[1][3];
vector<ll> ans = gen({x,y,z,rx,ry,rz});
return ans;
}
bool sub2 = m%2==0;
for(ll i = 0;i<m;i+=2) sub2&=(U[i]==V[i+1]&&V[i]==U[i+1]);
if(n<=1000&&sub2){
dfs1(1,1);
if(!naso) return naso;
if(tip==1){
ll A = -1,B = -1;
for(ll s : g[x]){
if(s==y) continue;
if(A==-1) A = s;
else if(B==-1) B = s;
}
ll x1 = id[x][A];
ll rx1 = id[A][x];
ll y1 = id[x][B];
ll ry1 = id[B][x];
vector<ll> ans;
for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
ans.pb(x1);
ans.pb(rx1);
ans.pb(y1);
ans.pb(ry1);
ans.pb(rx1);
ans.pb(x1);
ans.pb(ry1);
ans.pb(y1);
for(ll i = cur.size()-2;i>=0;i--) ans.pb(id[cur[i]][cur[i+1]]);
return ans;
}else{
ll x1 = allid[x][y][0];
ll y1 = allid[x][y][1];
ll rx1 = allid[y][x][0];
ll ry1 = allid[y][x][1];
vector<ll> ans;
for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
ans.pb(x1);
ans.pb(rx1);
ans.pb(y1);
ans.pb(x1);
ans.pb(rx1);
ans.pb(y1);
for(ll i = cur.size()-2;i>=0;i--) ans.pb(id[cur[i]][cur[i+1]]);
return ans;
}
}
dfs2(1,1);
if(!naso) return naso;
for(ll i = 1;i<=n;i++) vis[i] = 0;
reverse(all(cyc));
cur.clear();
naso = 0;
dfs3(1,1,cyc[0]);
cyc.pb(cyc[0]);
vector<ll> ans;
for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
for(ll i = 0;i<cyc.size()-1;i++) ans.pb(allid[cyc[i]][cyc[i+1]][0]);
for(ll i = 0;i<cyc.size()-1;i++) ans.pb(allid[cyc[i]][cyc[i+1]][1]);
for(ll i = cyc.size()-2;i>=0;i--) ans.pb(allid[cyc[i]][cyc[i+1]][0]);
for(ll i = cyc.size()-2;i>=0;i--) ans.pb(allid[cyc[i]][cyc[i+1]][1]);
for(ll i = cur.size()-2;i>=0;i--) ans.pb(id[cur[i]][cur[i+1]]);
return ans;
}
/**
5 8
0 1
1 0
1 2
2 1
2 3
3 2
2 4
4 2
7 14
0 1
0 1
1 2
1 2
2 3
2 3
3 4
3 4
4 5
4 5
5 6
5 6
6 3
6 3
**/
Compilation message
islands.cpp: In function 'std::vector<int> gen(std::vector<int>)':
islands.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(ll i = 0;i<=v.size()/2-1;i++) ans.pb(v[i]);
| ~^~~~~~~~~~~~~~
islands.cpp:24:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(ll i = v.size()-1;i>=v.size()/2;i--) ans.pb(v[i]);
| ~^~~~~~~~~~~~
islands.cpp:26:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(ll i = v.size()/2;i<=v.size()-1;i++) ans.pb(v[i]);
| ~^~~~~~~~~~~~
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:105:25: warning: unused variable 'y' [-Wunused-variable]
105 | ll x = U[i],y = V[i];
| ^
islands.cpp:129:31: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
129 | if(sub&&n<=400&&sss.size()==n*(n-1)&&m==n*(n-1)){
| ~~~~~~~~~~^~~~~~~~~
islands.cpp:156:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
| ~^~~~~~~~~~~~~
islands.cpp:173:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
| ~^~~~~~~~~~~~~
islands.cpp:171:16: warning: unused variable 'ry1' [-Wunused-variable]
171 | ll ry1 = allid[y][x][1];
| ^~~
islands.cpp:193:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
193 | for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
| ~^~~~~~~~~~~~~
islands.cpp:194:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for(ll i = 0;i<cyc.size()-1;i++) ans.pb(allid[cyc[i]][cyc[i+1]][0]);
| ~^~~~~~~~~~~~~
islands.cpp:195:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for(ll i = 0;i<cyc.size()-1;i++) ans.pb(allid[cyc[i]][cyc[i+1]][1]);
| ~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24020 KB |
Output is correct |
2 |
Correct |
13 ms |
24148 KB |
Output is correct |
3 |
Correct |
13 ms |
24020 KB |
Output is correct |
4 |
Correct |
12 ms |
24020 KB |
Output is correct |
5 |
Correct |
14 ms |
23964 KB |
Output is correct |
6 |
Correct |
13 ms |
24028 KB |
Output is correct |
7 |
Correct |
47 ms |
28104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24020 KB |
Output is correct |
2 |
Correct |
13 ms |
23952 KB |
Output is correct |
3 |
Correct |
12 ms |
24068 KB |
Output is correct |
4 |
Correct |
12 ms |
24072 KB |
Output is correct |
5 |
Correct |
13 ms |
24032 KB |
Output is correct |
6 |
Correct |
159 ms |
41464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
28372 KB |
Output is correct |
2 |
Correct |
14 ms |
24448 KB |
Output is correct |
3 |
Correct |
13 ms |
23972 KB |
Output is correct |
4 |
Correct |
14 ms |
24020 KB |
Output is correct |
5 |
Correct |
20 ms |
28244 KB |
Output is correct |
6 |
Correct |
12 ms |
24048 KB |
Output is correct |
7 |
Correct |
15 ms |
28056 KB |
Output is correct |
8 |
Correct |
14 ms |
24404 KB |
Output is correct |
9 |
Correct |
13 ms |
24472 KB |
Output is correct |
10 |
Correct |
17 ms |
28244 KB |
Output is correct |
11 |
Correct |
14 ms |
24020 KB |
Output is correct |
12 |
Correct |
16 ms |
28244 KB |
Output is correct |
13 |
Correct |
13 ms |
24404 KB |
Output is correct |
14 |
Correct |
13 ms |
24376 KB |
Output is correct |
15 |
Correct |
12 ms |
24360 KB |
Output is correct |
16 |
Correct |
13 ms |
24412 KB |
Output is correct |
17 |
Correct |
117 ms |
37432 KB |
Output is correct |
18 |
Correct |
86 ms |
35680 KB |
Output is correct |
19 |
Correct |
13 ms |
24044 KB |
Output is correct |
20 |
Correct |
13 ms |
24004 KB |
Output is correct |
21 |
Correct |
13 ms |
24020 KB |
Output is correct |
22 |
Correct |
12 ms |
24104 KB |
Output is correct |
23 |
Correct |
169 ms |
41420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24404 KB |
Output is correct |
2 |
Correct |
14 ms |
24532 KB |
Output is correct |
3 |
Correct |
62 ms |
28768 KB |
Output is correct |
4 |
Correct |
102 ms |
36584 KB |
Output is correct |
5 |
Correct |
20 ms |
27828 KB |
Output is correct |
6 |
Correct |
16 ms |
27808 KB |
Output is correct |
7 |
Correct |
13 ms |
24020 KB |
Output is correct |
8 |
Correct |
15 ms |
24032 KB |
Output is correct |
9 |
Correct |
12 ms |
24020 KB |
Output is correct |
10 |
Correct |
17 ms |
28164 KB |
Output is correct |
11 |
Correct |
20 ms |
28244 KB |
Output is correct |
12 |
Correct |
20 ms |
28244 KB |
Output is correct |
13 |
Correct |
16 ms |
28244 KB |
Output is correct |
14 |
Correct |
16 ms |
28124 KB |
Output is correct |
15 |
Correct |
17 ms |
28244 KB |
Output is correct |
16 |
Correct |
17 ms |
28116 KB |
Output is correct |
17 |
Correct |
14 ms |
24152 KB |
Output is correct |
18 |
Correct |
16 ms |
28124 KB |
Output is correct |
19 |
Correct |
15 ms |
28104 KB |
Output is correct |
20 |
Correct |
77 ms |
29084 KB |
Output is correct |
21 |
Correct |
114 ms |
37628 KB |
Output is correct |
22 |
Correct |
15 ms |
28116 KB |
Output is correct |
23 |
Correct |
14 ms |
28040 KB |
Output is correct |
24 |
Correct |
12 ms |
24404 KB |
Output is correct |
25 |
Correct |
13 ms |
24532 KB |
Output is correct |
26 |
Correct |
16 ms |
28244 KB |
Output is correct |
27 |
Correct |
109 ms |
35684 KB |
Output is correct |
28 |
Correct |
109 ms |
36300 KB |
Output is correct |
29 |
Correct |
13 ms |
24404 KB |
Output is correct |
30 |
Correct |
134 ms |
38688 KB |
Output is correct |
31 |
Correct |
13 ms |
24096 KB |
Output is correct |
32 |
Correct |
103 ms |
36592 KB |
Output is correct |
33 |
Correct |
68 ms |
29092 KB |
Output is correct |
34 |
Correct |
64 ms |
33640 KB |
Output is correct |
35 |
Correct |
14 ms |
26360 KB |
Output is correct |
36 |
Correct |
94 ms |
35800 KB |
Output is correct |
37 |
Correct |
116 ms |
38196 KB |
Output is correct |
38 |
Correct |
15 ms |
26068 KB |
Output is correct |
39 |
Correct |
87 ms |
33204 KB |
Output is correct |
40 |
Correct |
16 ms |
28116 KB |
Output is correct |
41 |
Correct |
127 ms |
38728 KB |
Output is correct |
42 |
Correct |
105 ms |
36544 KB |
Output is correct |
43 |
Correct |
13 ms |
24404 KB |
Output is correct |
44 |
Correct |
17 ms |
28180 KB |
Output is correct |
45 |
Correct |
16 ms |
28216 KB |
Output is correct |
46 |
Correct |
51 ms |
32460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24020 KB |
Output is correct |
2 |
Correct |
13 ms |
24148 KB |
Output is correct |
3 |
Correct |
13 ms |
24020 KB |
Output is correct |
4 |
Correct |
12 ms |
24020 KB |
Output is correct |
5 |
Correct |
14 ms |
23964 KB |
Output is correct |
6 |
Correct |
13 ms |
24028 KB |
Output is correct |
7 |
Correct |
47 ms |
28104 KB |
Output is correct |
8 |
Correct |
12 ms |
24020 KB |
Output is correct |
9 |
Correct |
13 ms |
23952 KB |
Output is correct |
10 |
Correct |
12 ms |
24068 KB |
Output is correct |
11 |
Correct |
12 ms |
24072 KB |
Output is correct |
12 |
Correct |
13 ms |
24032 KB |
Output is correct |
13 |
Correct |
159 ms |
41464 KB |
Output is correct |
14 |
Correct |
18 ms |
28372 KB |
Output is correct |
15 |
Correct |
14 ms |
24448 KB |
Output is correct |
16 |
Correct |
13 ms |
23972 KB |
Output is correct |
17 |
Correct |
14 ms |
24020 KB |
Output is correct |
18 |
Correct |
20 ms |
28244 KB |
Output is correct |
19 |
Correct |
12 ms |
24048 KB |
Output is correct |
20 |
Correct |
15 ms |
28056 KB |
Output is correct |
21 |
Correct |
14 ms |
24404 KB |
Output is correct |
22 |
Correct |
13 ms |
24472 KB |
Output is correct |
23 |
Correct |
17 ms |
28244 KB |
Output is correct |
24 |
Correct |
14 ms |
24020 KB |
Output is correct |
25 |
Correct |
16 ms |
28244 KB |
Output is correct |
26 |
Correct |
13 ms |
24404 KB |
Output is correct |
27 |
Correct |
13 ms |
24376 KB |
Output is correct |
28 |
Correct |
12 ms |
24360 KB |
Output is correct |
29 |
Correct |
13 ms |
24412 KB |
Output is correct |
30 |
Correct |
117 ms |
37432 KB |
Output is correct |
31 |
Correct |
86 ms |
35680 KB |
Output is correct |
32 |
Correct |
13 ms |
24044 KB |
Output is correct |
33 |
Correct |
13 ms |
24004 KB |
Output is correct |
34 |
Correct |
13 ms |
24020 KB |
Output is correct |
35 |
Correct |
12 ms |
24104 KB |
Output is correct |
36 |
Correct |
169 ms |
41420 KB |
Output is correct |
37 |
Partially correct |
12 ms |
24036 KB |
Output is partially correct |
38 |
Correct |
14 ms |
23956 KB |
Output is correct |
39 |
Incorrect |
13 ms |
24404 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |