This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
int n; vi deg(1000);
int mat[1000][1000][2];
/*
vi ans; vi p(1000,-1); vi used(1000);
void dfs(int u){
used[u]=1;
FOR(v,0,n){
if (mat[u][v][0] == -1) continue;
if (p[u]==v) continue;
if (mat[u][v][1] != -1){
//cout << "PATH\n";
vi path;
int w = u;
while (w != 0){
path.pb(w); w=p[w];
}
path.pb(0);
ROF(i,path.size()-1,1){
ans.pb(mat[path[i]][path[i-1]][0]);
}
//e0[0], e1[0], e0[1], e0[0], e1[0], e0[1]
vi path2 = {mat[u][v][0], mat[v][u][0], mat[u][v][1]};
FOR(i,0,2){
FOR(j,0,3) ans.pb(path2[j]);
}
FOR(i,1,path.size()){
ans.pb(mat[path[i]][path[i-1]][0]);
}
return;
}
if (used[v]){
// cycle 0-v-u
//cout << "CYCLE\n";
vi path;
int w = v;
while (w != 0){
path.pb(w); w=p[w];
}
path.pb(0);
//path 0-v
ROF(i,path.size()-1,1){
ans.pb(mat[path[i]][path[i-1]][0]);
}
vi cyc;
w = u;
while (w != v && w != 0){
cyc.pb(w); w=p[w];
}
cyc.pb(v);
//cycle 1
ans.pb(mat[v][u][0]);
FOR(i,1,cyc.size()){
ans.pb(mat[cyc[i-1]][cyc[i]][0]);
}
//cycle 2
ROF(i,cyc.size()-1,1){
ans.pb(mat[cyc[i]][cyc[i-1]][0]);
}
ans.pb(mat[u][v][0]);
//reverse cycle 1
ROF(i,cyc.size()-1,1){
ans.pb(mat[cyc[i-1]][cyc[i]][0]);
}
ans.pb(mat[v][u][0]);
//reverse cycle 2
ans.pb(mat[u][v][0]);
FOR(i,1,cyc.size()){
ans.pb(mat[cyc[i]][cyc[i-1]][0]);
}
//path v-0
FOR(i,1,path.size()){
ans.pb(mat[path[i]][path[i-1]][0]);
}
return;
}
if (deg[v] >= 3){
vi path;
int w = v;
while (w != 0){
path.pb(w); w=p[w];
}
//path 0-v
path.pb(0);
ROF(i,path.size()-1,1){
ans.pb(mat[path[i]][path[i-1]][0]);
}
vi x;
FOR(i,0,n){
if (mat[v][i][0]==-1) continue;
if (u==i) continue;
x.pb(i);
if (x.size()==2) break;
}
vi sh = {mat[v][x[0]][0], mat[x[0]][v][0], mat[v][x[1]][0], mat[x[1]][v][0],
mat[x[0]][v][0], mat[v][x[0]][0], mat[x[1]][v][0], mat[v][x[1]][0]};
FOR(i,0,8) ans.pb(sh[i]);
//path v-0
FOR(i,1,path.size()){
ans.pb(mat[path[i]][path[i-1]][0]);
}
return;
}
p[v] = u; used[v] = 1;
dfs(v);
}
}
*/
variant<bool, vi> find_journey(int N, int M, vi U, vi V) {
n=N;
if (N == 2){
vi e0, e1;
FOR(i,0,M){
if (U[i]==0) e0.pb(i);
else e1.pb(i);
}
if (e0.size() < 2 || e1.size() < 1) return false;
return vi({e0[0], e1[0], e0[1], e0[0], e1[0], e0[1]});
}
/*
if (N <= 400 && M == N*(N-1)){
vii p = {{0,1},{1,2},{2,0},{0,2},{2,1},{1,0}};
vi l(6);
FOR(i,0,M){
FOR(j,0,6){
if (p[j] == ii({U[i],V[i]})){
l[j] = i;
}
}
}
return vi({l[0],l[1],l[2],l[3],l[4],l[5],l[2],l[1],l[0],l[5],l[4],l[3]});
}
*/
if (N <= 1000 && U[0] != U[1]){
ms(mat, -1, sizeof(mat));
FOR(i,0,M){
// labelling edges
int pos = 0;
if (mat[U[i]][V[i]][0] != -1) pos = 1;
mat[U[i]][V[i]][pos] = i;
if (!pos) deg[U[i]]++;
}
/*
dfs(0);
if (ans.empty()) return false;
return ans;
*/
vi p(N,-1);
vi bfs; bfs.pb(0);
vi used(N); used[0] = 1;
FOR(k,0,bfs.size()){
int u = bfs[k];
FOR(i,0,N){
if (mat[u][i][0] == -1) continue;
if (used[i] && p[u] != i){
// cycle found
vi paru; int v = u;
while (v != 0){
paru.pb(v);
v = p[v];
}
paru.pb(0);
vi pari; v = i;
while (v != 0){
pari.pb(v); v = p[v];
}
pari.pb(0);
reverse(paru.begin(),paru.end());
reverse(pari.begin(),pari.end());
int a = 0;
vi ans;
//path from 0 to cycle
FOR(j,1,min(paru.size(),pari.size())){
if (paru[j] == pari[j]){
ans.pb(mat[paru[j-1]][paru[j]][0]);
a=j;
}else{
break;
}
}
//first loop
FOR(j,a+1,paru.size()){
ans.pb(mat[paru[j-1]][paru[j]][0]);
}
ans.pb(mat[u][i][0]);
ROF(j,pari.size()-1,a+1){
ans.pb(mat[pari[j]][pari[j-1]][0]);
}
//second loop
FOR(j,a+1,pari.size()){
ans.pb(mat[pari[j-1]][pari[j]][0]);
}
ans.pb(mat[i][u][0]);
ROF(j,paru.size()-1,a+1){
ans.pb(mat[paru[j]][paru[j-1]][0]);
}
//reverse 1st loop
FOR(j,a+1,pari.size()){
ans.pb(mat[pari[j]][pari[j-1]][0]);
}
ans.pb(mat[u][i][0]);
ROF(j,paru.size()-1,a+1){
ans.pb(mat[paru[j-1]][paru[j]][0]);
}
//reverse 2nd loop
FOR(j,a+1,paru.size()){
ans.pb(mat[paru[j]][paru[j-1]][0]);
}
ans.pb(mat[i][u][0]);
ROF(j,pari.size()-1,a+1){
ans.pb(mat[pari[j-1]][pari[j]][0]);
}
//path back to 0
ROF(j,a,1){
ans.pb(mat[paru[j]][paru[j-1]][0]);
}
return ans;
}
if (mat[u][i][1] != -1 && p[u] != i){
// double edge found, solution from Subtask 1
vi par; int v = u;
while (v != 0){
par.pb(v);
v = p[v];
}
par.pb(0);
reverse(par.begin(), par.end());
vi ans;
FOR(j,0,par.size()-1){
ans.pb(mat[par[j]][par[j+1]][0]); //path 0 -> u
}
// e0[0], e1[0], e0[1], e0[0], e1[0], e0[1]
vi path = {mat[u][i][0], mat[i][u][0], mat[u][i][1], mat[u][i][0], mat[i][u][0], mat[u][i][1]};
FOR(j,0,6) ans.pb(path[j]);
ROF(j,par.size()-2,0){
ans.pb(mat[par[j]][par[j+1]][0]); //path u -> 0
}
return ans;
}
if (deg[i] >= 3){
vi path, ans; path.pb(i);
int w = u;
while (w != 0){
path.pb(w); w=p[w];
}
//path 0-i
path.pb(0);
ROF(j,path.size()-1,1){
ans.pb(mat[path[j]][path[j-1]][0]);
}
vi x;
FOR(j,0,n){
if (mat[i][j][0]==-1) continue;
if (u==j) continue;
x.pb(j);
if (x.size()==2) break;
}
vi sh = {mat[i][x[0]][0], mat[x[0]][i][0], mat[i][x[1]][0], mat[x[1]][i][0],
mat[x[0]][i][0], mat[i][x[0]][0], mat[x[1]][i][0], mat[i][x[1]][0]};
FOR(j,0,8) ans.pb(sh[j]);
//path i-0
FOR(j,1,path.size()){
ans.pb(mat[path[j]][path[j-1]][0]);
}
return ans;
}
if (used[i]) continue;
used[i] = 1; p[i] = u;
bfs.pb(i);
}
}
}
return false;
}
Compilation message (stderr)
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, vi, vi)':
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
173 | FOR(k,0,bfs.size()){
| ~~~~~~~~~~~~~~
islands.cpp:173:5: note: in expansion of macro 'FOR'
173 | FOR(k,0,bfs.size()){
| ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
195 | FOR(j,1,min(paru.size(),pari.size())){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:195:11: note: in expansion of macro 'FOR'
195 | FOR(j,1,min(paru.size(),pari.size())){
| ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
204 | FOR(j,a+1,paru.size()){
| ~~~~~~~~~~~~~~~~~
islands.cpp:204:11: note: in expansion of macro 'FOR'
204 | FOR(j,a+1,paru.size()){
| ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
212 | FOR(j,a+1,pari.size()){
| ~~~~~~~~~~~~~~~~~
islands.cpp:212:11: note: in expansion of macro 'FOR'
212 | FOR(j,a+1,pari.size()){
| ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
220 | FOR(j,a+1,pari.size()){
| ~~~~~~~~~~~~~~~~~
islands.cpp:220:11: note: in expansion of macro 'FOR'
220 | FOR(j,a+1,pari.size()){
| ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
228 | FOR(j,a+1,paru.size()){
| ~~~~~~~~~~~~~~~~~
islands.cpp:228:11: note: in expansion of macro 'FOR'
228 | FOR(j,a+1,paru.size()){
| ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
251 | FOR(j,0,par.size()-1){
| ~~~~~~~~~~~~~~~~
islands.cpp:251:11: note: in expansion of macro 'FOR'
251 | FOR(j,0,par.size()-1){
| ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
285 | FOR(j,1,path.size()){
| ~~~~~~~~~~~~~~~
islands.cpp:285:11: note: in expansion of macro 'FOR'
285 | FOR(j,1,path.size()){
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |