| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1265251 | canhnam357 | 슈퍼트리 잇기 (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> par;
vector<vector<int>> cc;
dsu(int n) {
par.resize(n);
cc.resize(n);
for (int i = 0; i < n; i++) cc[i].push_back(i);
iota(par.begin(), par.end(), 0);
}
int find(int u) {
return u == par[u] ? u : par[u] = find(par[u]);
}
void join(int a, int b) {
a = find(a), b = find(b);
if (a != b) {
if (cc[a].size() > cc[b].size()) swap(a, b);
par[a] = b;
for (int i : cc[a]) cc[b].push_back(i);
}
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 3) return 0;
}
}
dsu e1(n), e(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i][j] == 1) e1.join(i, j);
if (p[i][j]) e.join(i, j);
}
}
for (int i = 0; i < n; i++) {
if (e.par[i] == i) {
for (int a : e.cc[i]) {
for (int b : e.cc[i]) {
if (!p[a][b]) return 0;
}
}
}
}
for (int i = 0; i < n; i++) {
if (e1.par[i] == i) {
for (int a : e1.cc[i]) {
for (int b : e1.cc[i]) {
if (p[a][b] != 1) return 0;
}
}
}
}
vector<pair<int, int>> edge;
for (int i = 0; i < n; i++) {
if (e1.par[i] == i) {
for (int j = 1; j < e1.cc[i].size(); j++) {
edge.emplace_back(e1.cc[i][j - 1], e1.cc[i][j]);
}
}
}
vector<vector<int>> res(n, vector<int>(n));
for (auto [u, v] : edge) res[u][v] = res[v][u] = 1;
build(res);
return 1;
}
int main() {}