| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1021437 | Wael | 열쇠 (IOI21_keys) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "grader.cpp"
using namespace std;
struct DSU {
int n, cnt;
vector<int> f, sz;
vector<vector<int>> keys;
DSU(int n, vector<int> r) : n(n), cnt(n) {
f.resize(n);
iota(f.begin(), f.end(), 0);
sz.resize(n, 1);
keys.resize(n);
for (int i = 0; i < n; ++i) {
keys[i].push_back(r[i]);
}
}
int find(int u) {
if (f[u] == u) return u;
return f[u] = find(f[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
--cnt;
if (sz[v] > sz[u]) {
swap(u, v);
}
f[v] = u;
sz[u] += sz[v];
for (auto k : keys[v]) {
keys[u].push_back(k);
}
vector<int>().swap(keys[v]);
}
bool same(int u, int v) {
return find(u) == find(v);
}
};
vector<int> find_reachable(vector<int> r, std::vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
int m = u.size();
vector<vector<int>> edges(n);
for (int j = 0; j < m; ++j) {
edges[c[j]].push_back(j);
}
vector<int> p(n);
for (int i = 0; i < n; ++i) {
DSU dsu(n, r);
vector<int> vis(n);
vector<int> have;
have.push_back(r[i]);
while (have.size()) {
int k = have.back();
have.pop_back();
if (vis[k]) {
continue;
}
vis[k] = 1;
for (auto j : edges[k]) {
auto [x, y] = make_pair(u[j], v[j]);
if (dsu.same(x, y)) {
continue;
}
if (dsu.same(i, y)) {
swap(x, y);
}
if (dsu.same(i, x)) {
for (auto z : dsu.keys[y]) {
have.push_back(z);
}
}
dsu.merge(x, y);
}
}
p[i] = dsu.sz[dsu.find(i)];
}
int mn = *min_element(p.begin(), p.end());
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[i] = (p[i] == mn);
}
return ans;
}