| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 598760 | Bobaa | 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 + 10;
int par[maxn], sz[maxn], bad[maxn], state[maxn], lst[maxn];
map<int, vector<int>> g[maxn];
set<int> key[maxn];
vector<int> to[maxn];
namespace dsu {
int Find(int u) {
return (u == par[u] ? u : par[u] = find(par[u]));
}
void Union(int u, int v) {
if ((u = Find(u)) == (v = Find(v))) return;
if (sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
if (key[u].size() + to[u].size() < key[v].size() + to[v].size()) {
swap(key[u], key[v]);
swap(to[u], to[v]);
}
for (auto w : to[v]) to[u].push_back(w);
to[v].clear();
for (auto c : key[v]) if (g[u].find(c) != g[u].end()) {
for (auto w : g[u][c]) to[u].push_back(w);
g[u].erase(c);
}
for (auto [c, _] : g[v]) {
if (g[u].find(c) != g[u].end()) for (auto w : g[v][c]) to[u].push_back(w);
else for (auto w : g[v][c]) g[u][c].push_back(w);
}
g[v].clear();
key[u].insert(key[v].begin(), key[v].end());
key[v].clear();
}
}
using namespace dsu;
void dfs(int u) {
state[u] = 0;
while (1) {
u = Find(u);
if (to[u].empty()) break;
int v = to[u].back();
to[u].pop_back();
v = Find(v);
if (u == v) continue;
if (state[v] == -1) {
lst[v] = u;
dfs(v);
if (Find(u) != Find(v)) bad[u] = 1;
} else if (state[v] == 0) {
int w = u;
while (1) {
if (Find(w) == Find(v)) break;
Union(w, v);
w = lst[w];
}
} else bad[u] = 1;
}
state[u] = 1;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size(), m = c.size();
auto adde = [&](int u, int v, int c) {
if (r[u] == c) to[u].push_back(v);
else g[u][c].push_back(v);
};
for (int i = 0; i < m; i++) {
adde(u[i], v[i], c[i]);
adde(v[i], u[i], c[i]);
}
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
key[i].insert(r[i]);
}
memset(state, -1, sizeof(state));
for (int i = 0; i < n; i++) if (state[i] == -1) dfs(i);
for (int i = 0; i < n; i++) if (bad[i]) bad[Find(i)] = 1;
vector<int> flg(n, 0);
int ans = 1e9;
for (int i = 0; i < n; i++) if (i == Find(i) && !bad[i]) ans = min(ans, sz[i]);
for (int i = 0; i < n; i++) if (!bad[Find(i)] && sz[Find(i)] == ans) flg[i] = 1;
return flg;
}