| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 728620 | grogu | Thousands Islands (IOI22_islands) | C++17 | 0 ms | 0 KiB |
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"
#define here cerr<<"=======================\n"
#include <iostream>
#include <vector>
#include <variant>
#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
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;
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 = 1;
for(ll i = 1;i<=n;i++) for(ll j = 1;j<=n;j++) sub2&=(allid[i][j]%2==0);
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;
}
}
}
/**
5 8
0 1
1 0
1 2
2 1
2 3
3 2
2 4
4 2
**/