| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 826406 | alvingogo | 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"
#include <bits/stdc++.h>
#include <variant>
#define fs first
#define sc second
using namespace std;
vector<vector<pair<int,int> > > e;
vector<int> dep,fa;
vector<int> ss;
vector<int> ans;
int dfs(int r,int f){
dep[r]=dep[f]+1;
fa[r]=f;
for(auto h:e[r]){
if(ss[h.sc/2]){
continue;
}
ss[h.sc/2]=1;
if(dep[h.fs]==-1){
if(dfs(h.fs,r)){
return 1;
}
}
else if(dep[h.fs]>=0){
return 1;
}
}
dep[r]=-2;
return 0;
}
variant<bool, vector<int>> find_journey(
int n, int m, vector<int> u, vector<int> v) {
e.resize(n);
fa.resize(n);
ss.resize(m);
dep.resize(n,-1);
for(int i=0;i<m;i++){
e[u[i]].push_back({v[i],i});
}
dfs(0,0);
ans.clear();
if(e[0].size()>=2){
ans={e[0][0].sc,e[0][0].sc^1,e[0][1].sc,e[0][1].sc^1,e[0][0].sc^1,e[0][0].sc,e[0][1].sc^1,e[0][1].sc};
return ans;
}
for(int i=1;i<n;i++){
if(dep[i]!=-1){
if(deg[i]>=3){
vector<int> bz;
vector<int> vs(m);
for(int j=i;j!=0;){
for(auto w:e[j]){
if(fa[j]==w.fs){
bz.push_back(w.sc);
vs[w.sc/2]=1;
j=w.fs;
break;
}
}
}
int ct=0;
vector<int> y;
ans.insert(ans.end(),bz.begin(),bz.end());
for(auto h:e[i]){
if(!vs[h.sc/2]){
ct++;
y.push_back(h.sc);
if(ct==2){
break;
}
}
}
ans.push_back(y[0]);
ans.push_back(y[0]^1);
ans.push_back(y[1]);
ans.push_back(y[1]^1);
ans.push_back(y[0]^1);
ans.push_back(y[0]);
ans.push_back(y[1]^1);
ans.push_back(y[1]);
reverse(bz.begin(),bz.end());
ans.insert(ans.end(),bz.begin(),bz.end());
return ans;
}
}
}
return false;
}