| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1338047 | vidux | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
int construct(vvi p) {
int n = p.size();
vvi ans(n, vi(n));
vvi comp(n);
vi seen(n);
bool ok = 1;
for (int c = 0; c < n; c++) {
auto dfs = [&](auto dfs, int u) -> void {
if (seen[u]) return;
seen[u] = 1;
comp[c].push_back(u);
for (int v = 0; v < n; v++) {
if (p[u][v]) {
if (p[u][v] == 3) ok = 0;
dfs(dfs, v);
}
}
};
dfs(dfs, c);
}
if (!ok) return 0;
for (int u = 0; u < n; u++) for (int v = 0; v < n; v++) if (seen[u] != seen[v] && p[u][v]) return 0;
for (int c = 0; c < n; c++) if (comp[c].size()) {
vi ones, twos, mix;
for (int u : comp[c]) {
vi cnt(3);
for (int v : comp[c]) if (u != v) cnt[p[u][v]]++;
if (cnt[1] && !cnt[2]) ones.push_back(u);
else if (cnt[2] && !cnt[1]) twos.push_back(u);
else mix.push_back(u);
}
if (twos.empty() && ones.size()) {
int prev = -1;
for (int u : ones) {
if (prev >= 0) ans[u][prev] = ans[prev][u] = 1;
prev = u;
}
}
else if (twos.size()) {
if (ones.size()) return 0;
int prev = -1;
for (int u : twos) {
if (prev >= 0) ans[u][prev] = ans[prev][u] = 1;
prev = u;
}
if (mixed.empty()) {
if (twos.size() < 3) return 0;
ans[twos[0]][twos.back()] = ans[twos.back()][twos[0]] = 1;
}
else {
if (twos.size() < 2) return 0;
int prev = -1;
for (int u : mixed) {
if (prev >= 0) ans[u][prev] = ans[prev][u] = 1;
prev = u;
}
ans[twos[0]][prev] = ans[prev][twos[0]] = 1;
ans[twos.back()][prev] = ans[prev][twos.back()] = 1;
}
}
}
build(ans);
return 1;
}