| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 448740 | grt | 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>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 300 * 1000 + 10;
int n, m;
vector<pi>V[nax];
int par[nax];
set<int>reach[nax];
int p[nax], deg[nax];
vi vertices[nax];
bool done[nax];
map<int, vi> graph[nax];
vi edges[nax];
int G[nax];
int p2[nax], siz[nax];
int Fund(int x) {
if(p2[x] != x) p2[x] = Fund(p2[x]);
return p2[x];
}
bool Onion(int a, int b) {
a = Fund(a); b = Fund(b);
if(a == b) return false;
if(siz[a] < siz[b]) swap(a, b);
p2[b] = a;
siz[a] += siz[b];
return true;
}
void merge(int a, int b) {
if(p[a] == p[b]) return;
if((int)vertices[p[a]].size() < (int)vertices[p[b]].size()) swap(a, b);
int pb = p[b];
if(G[p[a]] < G[pb]) {
swap(G[p[a]], G[pb]);
reach[p[a]].swap(reach[pb]);
graph[pb].swap(graph[p[a]]);
}
for(auto &it : graph[pb]) {
if(reach[p[a]].count(it.ST)) {
for(int &x : it.ND) {
edges[p[a]].PB(x);
}
} else {
for(int &x : it.ND) {
graph[p[a]][it.ST].PB(x);
}
}
}
G[p[a]] += G[pb];
graph[pb].clear();
for(int x : vertices[pb]) {
p[x] = p[a];
vertices[p[a]].PB(x);
}
for(int x : reach[pb]) {
if(!reach[p[a]].count(x)) {
for(int &y : graph[p[a]][x]) {
edges[p[a]].PB(y);
}
graph[p[a]][x].clear();
}
reach[p[a]].insert(x);
}
if((int)edges[p[a]].size() < (int)edges[pb].size()) edges[p[a]].swap(edges[pb]);
for(int x : edges[pb]) {
edges[p[a]].PB(x);
}
edges[pb].clear();
vertices[pb].clear();
reach[pb].clear();
}
vi find_reachable(vi r, vi u, vi v, vi c) {
n = (int)r.size();
m = (int)u.size();
for(int i = 0; i < m; ++i) {
V[u[i]].emplace_back(v[i], c[i]);
V[v[i]].emplace_back(u[i], c[i]);
}
vi tmp = {};
for(int i = 0; i < n; ++i) {
p2[i] = i; siz[i] = 1;
}
for(int i = 0; i < n; ++i) {
bool any = false;
for(auto nbh : V[i]) {
if(r[i] == nbh.ND) {
par[i] = nbh.ST;
edges[i].PB(nbh.ST);
any = true;
}
graph[i][nbh.ND].PB(nbh.ST);
}
G[i] = (int)V[i].size();
if(!any) {
tmp.PB(i);
}
reach[i].insert(r[i]);
vertices[i].PB(i);
p[i] = i;
deg[par[i]]++;
Onion(par[i], i);
}
if((int)tmp.size() > 0) {
vi ans(n);
for(int x : tmp) ans[x] = true;
return ans;
}
vi zeroDeg = {};
for(int i = 0; i < n; ++i) {
if(deg[i] == 0) {
zeroDeg.PB(i);
}
}
while((int)zeroDeg.size() > 0) {
int x = zeroDeg.back();
done[x] = true;
zeroDeg.pop_back();
deg[par[x]]--;
if(deg[par[x]] == 0) zeroDeg.PB(par[x]);
}
vi roots;
for(int i = 0; i < n; ++i) {
if(!done[i]) {
vi cycle = {i};
int x = i;
done[i] = true;
while(par[x] != i) {
x = par[x];
done[x] = true;
cycle.PB(x);
}
for(int j = 1; j < (int)cycle.size(); ++j) {
merge(cycle[j - 1], cycle[j]);
}
roots.PB(p[i]);
}
}
vector<vi>res;
while((int)roots.size() > 0) {
//for(int i = 0; i < n; ++i) {
//cout << p[i] << " ";
//}
//cout << "\n";
int x = roots.back();
if(edges[x].size() == 0) {
res.PB(vertices[x]);
roots.pop_back();
continue;
}
int y = edges[x].back();
edges[x].pop_back();
if(p[x] == p[y]) continue;
//cout << "MERGING: " << x << " " << y << "\n";
x = p[x]; y = p[y];
if(!Onion(x, y)) {
//cout << "OPT1\n";
vi path = {y};
while(p[par[y]] != x) {
//cerr << p[par[y]] << " " << x << "\n";
path.PB(p[par[y]]);
y = p[par[y]];
}
path.PB(x);
for(int j = 1; j < (int)path.size(); ++j) {
merge(path[j], path[j - 1]);
}
roots.pop_back();
roots.PB(p[path[0]]);
} else {
//cout << "OPT2\n";
par[x] = p[y];
roots.pop_back();
}
}
int mi = 1000000000;
for(auto &vec : res) {
mi = min(mi, (int)vec.size());
}
vi ans(n);
for(int i = 0; i < n; ++i) ans[i] = 0;
for(auto &vec : res) {
if((int)vec.size() == mi) {
for(int x : vec) {
ans[x] = 1;
}
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
vi r(N), u(M), v(M), c(M);
for(int i = 0; i < N; ++i) {
cin >> r[i];
}
for(int i = 0; i < M; ++i) {
cin >> u[i] >> v[i] >> c[i];
}
auto ans = find_reachable(r,u,v,c);
for(int x : ans) cout << x << " ";
}