# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
774160 | SanguineChameleon | 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>
using namespace std;
const int maxN = 3e5 + 20;
deque<int> Q;
struct comp {
set<int> rooms;
map<int, set<pair<int, int>>> edges;
set<int> cands, keys;
int edge_cnt = 0;
int id = -1;
int par = -1;
void add_cand(int k) {
if (par == -1 && cands.empty()) {
Q.push_back(id);
}
cands.insert(k);
}
void add_key(int k) {
keys.insert(k);
if (edges.find(k) != edges.end()) {
add_cand(k);
}
}
void add_edge(int u, int v, int k) {
if (u > v) {
swap(u, v);
}
if (edges[k].find(make_pair(u, v)) == edges[k].end()) {
edges[k].emplace(u, v);
edge_cnt++;
}
if (keys.find(k) != keys.end()) {
add_cand(k);
}
}
};
struct DSU {
int par[maxN];
int depth[maxN];
void init(int N) {
for (int i = 0; i < N; i++) {
par[i] = -1;
depth[i] = 0;
}
}
int root(int u) {
return (par[u] == -1 ? u : (par[u] = root(par[u])));
}
void join(int u, int v) {
u = root(u);
v = root(v);
if (depth[u] > depth[v]) {
swap(u, v);
}
par[u] = v;
if (depth[u] == depth[v]) {
depth[v]++;
}
}
} D;
comp comps[maxN];
int comp_id[maxN];
void merge(comp &X, comp &Y) {
/* if (X.rooms.size() > Y.rooms.size()) {
merge(Y, X);
return;
}*/
Y.par = -1;
for (auto u: X.rooms) {
comp_id[u] = Y.id;
Y.rooms.insert(u);
}
/* if (X.cands.size() > Y.cands.size()) {
swap(X.cands, Y.cands);
}*/
for (auto k: X.cands) {
Y.add_cand(k);
}
/* if (X.keys.size() > Y.keys.size()) {
swap(X.keys, Y.keys);
}*/
for (auto k: X.cands) {
Y.add_key(k);
}
/* if (X.edge_cnt > Y.edge_cnt) {
swap(X.edges, Y.edges);
swap(X.edge_cnt, Y.edge_cnt);
}*/
for (auto p: X.edges) {
int k = p.first;
for (auto e: p.second) {
int u = e.first;
int v = e.second;
Y.add_edge(u, v, k);
}
}
}
void expand(int X) {
if (comps[X].par != -1) {
return;
}
cands = keys;
while (!comps[X].cands.empty()) {
auto it1 = comps[X].cands.begin();
auto it2 = comps[X].edges.find(*it1);
auto it3 = it2->second.begin();
it2->second.erase(it3);
if (it2->second.empty()) {
comps[X].cands.erase(it1);
comps[X].edges.erase(it2);
}
int u = it3->first;
int v = it3->second;
if (comps[X].rooms.find(u) == comps[X].rooms.end()) {
swap(u, v);
}
if (D.root(u) != D.root(v)) {
D.join(u, v);
comps[X].par = comp_id[v];
return;
}
v = comp_id[v];
vector<int> path;
while (v != X) {
path.push_back(v);
v = comp_id[comps[v].par];
}
for (auto Y: path) {
merge(comps[Y], comps[X]);
X = comp_id[X];
}
}
}
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
int N = R.size();
int M = U.size();
D.init(N);
for (int i = 0; i < N; i++) {
comps[i].id = i;
comps[i].rooms.insert(i);
comp_id[i] = i;
comps[i].add_key(R[i]);
}
for (int i = 0; i < M; i++) {
comps[U[i]].add_edge(U[i], V[i], C[i]);
comps[V[i]].add_edge(U[i], V[i], C[i]);
}
while (!Q.empty()) {
expand(Q.front());
Q.pop_front();
}
int mi = N + 1;
for (int i = 0; i < N; i++) {
if (comps[comp_id[i]].par == -1) {
mi = min(mi, (int)comps[comp_id[i]].rooms.size());
}
}
vector<int> res(N);
for (int i = 0; i < N; i++) {
res[i] = (comps[comp_id[i]].par == -1 && (int)comps[comp_id[i]].rooms.size() == mi);
}
return res;
}