| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 486913 | MilosMilutinovic | 열쇠 (IOI21_keys) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
/*struct component {
int root;
set<int> keys;
void init(int u, int c) {
root = u;
keys.insert(c);
}
};*/
vector<int> resi(vector<int> c, vector<int> u, vector<int> v, vector<int> r) {
int n = c.size();
int m = u.size();
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
g[u[i]].emplace_back(v[i], r[i]);
g[v[i]].emplace_back(u[i], r[i]);
}
vector<set<int>> keys(n);
vector<vector<int>> ch(n);
vector<int> id(n);
for (int i = 0; i < n; i++) {
//comp[i].init(i, c[i]);
keys[i].insert(c[i]);
ch[i] = {i};
id[i] = i;
}
function<void(int, int)> Merge = [&](int u, int v) {
for (int i : keys[u]) {
keys[v].insert(i);
}
keys[u].clear();
for (int i : ch[u]) {
ch[v].push_back(i);
id[i] = v;
}
ch[u].clear();
};
vector<int> ans(n, 1e9);
for (int foo = 0; foo < 30; foo++) {
vector<bool> mrg(n, false);
for (int i = 0; i < n; i++) {
if (mrg[id[i]] || ans[id[i]] != 1e9) {
continue;
}
int other = -1;
set<int> s, vis;
map<int, vector<int>> mp;
function<void(int)> Dfs = [&](int u) {
if (other != -1 || vis.find(u) != vis.end()) {
return;
}
if (id[u] != id[i]) {
other = u;
return;
}
vis.insert(u);
s.insert(c[u]);
for (auto x : mp[c[u]]) {
Dfs(x);
if (other != -1) {
return;
}
}
mp[c[u]].clear();
for (auto e : g[u]) {
if (s.find(e.second) != s.end()) {
Dfs(e.first);
if (other != -1) {
return;
}
} else {
mp[e.second].push_back(e.first);
}
}
};
Dfs(id[i]);
if (other == -1) {
for (int u : vis) {
ans[u] = vis.size();
}
} else {
Merge(id[i], id[other]);
mrg[id[i]] = true;
mrg[id[other]] = true;
}
}
}
int mn = *min_element(ans.begin(), ans.end());
for (int i = 0; i < n; i++) {
ans[i] = (ans[i] == mn ? 1 : 0);
}
return ans;
}