| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 437692 | jeroenodb | Keys (IOI21_keys) | 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 "bits/stdc++.h"
#include "keys.h"
#include "grader.cpp"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int r){return std::uniform_int_distribution<int>(0,r-1)(rng);}
struct blockedges {
vvi blocked;
unordered_set<int> used;
blockedges(int n) {
blocked.resize(n);
}
void add(int r, int to) {
if(blocked[r].empty()) used.insert(r);
blocked[r].push_back(to);
}
void reset() {
for(int i:used) blocked[i].clear();
used.clear();
}
};
vi find_reachable(vi r, vi u, vi v, vi c) {
int n = r.size();
vvi adj(n);
int m=c.size();
for(int i=0;i<m;++i) {
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
}
for(int i=0;i<n;++i) {
random_shuffle(all(adj[i]),rnd);
}
vector<unordered_set<int>> sets(n);
vi par(n,-1);
vi order(n); iota(all(order),0);
random_shuffle(all(order),rnd);
vector<bool> done(n);
int minimum=oo;
blockedges bl(n);
for(auto start : order) {
bl.reset();
// Simulate process
stack<int> explore;
auto& vis = sets[start];
explore.push(start);
vis.insert(start);
while(!explore.empty()) {
int at = explore.top(); explore.pop();
vi& unblock = bl.blocked[r[at]];
auto explorefurther = [&]() {
while(!unblock.empty() and vis.size()<=minimum) {
int to = unblock.back(); unblock.pop_back();
if(!vis.count(to)) {
if(done[to]) {
if(sets[to].count(start)) {
// stop simulating
par[start] = par[to];
} else par[start]=-2;
break;
}
vis.insert(to);
explore.push(to);
}
}
};
explorefurther();
if(par[at]!=-1 or vis.size()>minimum) break;
for(int eid : adj[at]) {
int to = u[eid]^v[eid]^at;
bl.add(c[eid],to);
}
explorefurther();
if(par[at]!=-1 or vis.size()>minimum) break;
}
if(par[start]==-1 and vis.size()<=minimum) {
par[start]=start;
minimum = vis.size();
}
if(par[start]==-1) par[start]=-2;
done[start]=true;
}
vi ans(n,0);
for(int i=0;i<n;++i) {
if(par[i]>=0 and sets[par[i]].size()==minimum) ans[i]=1;
}
return ans;
}