| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 764410 | raysh07 | 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 <variant>
#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
const int M = 2e5 + 69;
vector <pair<int, int>> adj[N];
bool v1[N], vis[N];
int curr;
int n;
vector <int> path, ok[N], ok1;
pair <int, int> bruh[M];
int dep[N];
void dfs(int u){
vis[u] = true;
for (auto [v, i] : adj[u]){
if (v == curr && ok1.size() == 0){
path.push_back(i);
ok1 = path;
} else if (!vis[v]){
path.push_back(i);
dfs(v);
path.pop_back();
}
}
}
void dfs1(int u){
v1[u] = true;
ok[u] = path;
for (auto [v, i] : adj[u]){
if (!v1[v]){
dep[v] = dep[u] + 1;
path.push_back(i);
dfs1(v);
path.pop_back();
}
}
}
void add(vector <int> &a, vector <int> b, bool rev, int xo = 0){
if (rev) reverse(b.begin(), b.end());
for (auto x : b) a.push_back(x ^ xo);
}
vector <int> get(int i){
vector <int> ans;
int ong = 0;
add(ans, ok[i], false);
add(ans, ok1, false);
add(ans, ok1, false, 1);
add(ans, ok1, true);
add(ans, ok1, true, 1);
add(ans, ok[i], true);
for (auto x : ans){
if (ong != bruh[x].first) assert(false);
ong = bruh[x].second;
swap(bruh[x].first, bruh[x].second);
}
assert(ong == 0);
return ans;
}
bool comp(int x, int y) return dep[x] < dep[y];
variant<bool, vector<int>> find_journey(int nn, int m, vector<int> u, vector<int> v) {
n = nn;
for (int i = 0; i < m; i++){
bruh[i] = {u[i], v[i]};
}
for (int i = 0; i < m; i += 2){
adj[u[i]].push_back({v[i], i});
}
dfs1(0);
vector <int> perm;
for (int i = 0; i < n; i++) perm.push_back(i);
sort(perm.begin(), perm.end(), comp);
for (auto i : perm){
if (v1[i]){
curr = i;
path.clear();
//look for cycle starting and ending at i
//good if someone can reach curr
for (int j = 0; j < n; j++) vis[j] = false;
dfs(i);
if (ok1.size()) return get(i);
}
}
return false;
}