| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1058502 | mychecksedad | 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>
using namespace std;
#define pb push_back
#define en cout << '\n'
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
const int N = 1e5+10;
int n, m;
vector<pair<int, int>> g[N];
vector<int> euler, cyc;
vector<bool> good, in_euler(N);
bool is_cyc = 0;
map<pii, vi> A;
vector<int> S;
bool second_case = 0;
bool dfs(int v, int par, vector<bool> &vis){
vis[v] = 1;
euler.pb(v);
in_euler[v] = 1;
// cout << v << ' ';
for(auto U: g[v]){
int u = U.ss;
if(vis[u] && u != par && in_euler[u]){
// cout << v << ' ' << u << endl;
euler.pb(u);
cyc.pb(u);
cyc.pb(v);
is_cyc = 1;
return 1;
}
if(!vis[u] && A[{v, u}].size() > 1 && A[{u, v}].size() > 0){
second_case = 1;
// cout << "fuck" << endl;
is_cyc = 0;
S = vi{A[{v, u}][0], A[{u, v}][0], A[{v, u}][1], A[{v, u}][0], A[{u, v}][0], A[{v, u}][1]};
return 1;
}
if(!vis[u]){
bool ok = dfs(u, v, vis);
// cout << u << ' ' << v << ' ' << ok << endl;
if(is_cyc && ok) cyc.pb(v);
if(ok && is_cyc){
// assert(cyc.size());
if(v == cyc[0])
// cout << v << endl;
is_cyc = 0;
}
// cout << ok << ' ' << v << '\n';
if(ok) return 1;
}
}
assert(euler.size()>0);
euler.pop_back();
in_euler[v] = 0;
return 0;
}
std::variant<bool, std::vector<int>> find_journey(int nn, int mm, std::vector<int> U, std::vector<int> V) { n=nn, m=mm;
vector<vi> C(nn);
good.resize(n);
for(int i = 0; i < mm; ++i){
C[U[i]].pb(i);
g[U[i]].pb({i, V[i]});
A[{U[i], V[i]}].pb(i);
// if(A[{U[i], V[i]}].size() > 1) good[U[i]] = good[V[i]] = 1;
}
for(int i = 1; i < n; ++i){
if(A[{0, i}].size() > 1 && A[{i, 0}].size() > 0){
return vi{A[{0, i}][0], A[{i, 0}][0], A[{0, i}][1], A[{0, i}][0], A[{i, 0}][0], A[{0, i}][1]};
}
}
// if(!(C[0].size() > 1 && C[1].size() > 0)) return false;
vector<bool> vis(n);
// return false;
bool ok = dfs(0, 0, vis);
if(!ok){
return false;
}
vi res;
// for(int v: euler) cout << v << endl;
// for(int v: cyc) cout << v << endl;
// cout << A[{0, 1}][0] << ' ';
// en;en;
if(second_case){
for(int i = 0; i + 1 < euler.size(); ++i){
res.pb(A[{euler[i], euler[i + 1]}][0]);
// cout << res.back() << ' ';
// cout << euler[i] << ' ' << euler[i + 1] << '\n';
}
for(int x: S) res.pb(x);
vector<int> res2;
for(int i = 0; i + 1 < euler.size(); ++i){
res2.pb(A[{euler[i], euler[i + 1]}][0]);
}
reverse(all(res2));
for(int x: res2) res.pb(x);
return res;
}
for(int i = 0; i + 1 < euler.size(); ++i){
res.pb(A[{euler[i], euler[i + 1]}][0]);
}
// assert();
reverse(all(cyc));
assert(A[{cyc[0], cyc[1]}].size() > 0);
res.pb(A[{cyc[0], cyc[1]}][1]);
res.pb(A[{cyc[0], cyc[1]}][0]);
reverse(all(cyc));
// assert(false);
for(int i = 0; i + 2 < cyc.size(); ++i){
res.pb(A[{cyc[i], cyc[i + 1]}][0]);
}
// reverse(all(cyc));
res.pb(A[{cyc[0], cyc[1]}][1]);
// assert(false);
vi res2;
// for(int i = 0; i + 1 < cyc.size(); ++i){
// res2.pb(A[{cyc[i], cyc[i + 1]}][0]);
// }
// reverse(all(res2));
// for(int x: res2) res.pb(x);
// reverse(all(cyc));
// res2.clear();
// for(int i = 0; i + 1 < cyc.size(); ++i){
// res2.pb(A[{cyc[i], cyc[i + 1]}][0]);
// }
// reverse(all(res2));
// for(int x: res2) res.pb(x);
res2.clear();
for(int i = 0; i + 1 < euler.size(); ++i){
if(cyc[0] == euler[i]) break;
res2.pb(A[{euler[i], euler[i + 1]}][0]);
}
reverse(all(res2));
for(int x: res2) res.pb(x);
return res;
}