| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1355316 | Charizard2021 | 슈퍼트리 잇기 (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int> > adj;
vector<int> parent;
vector<bool> visited;
vector<int> e;
bool works = true;
vector<vector<int> > p;
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y){
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y]; e[y] = x;
return true;
}
void dfs(int u){
visited[u] = true;
for(int v = 0; v < n; v++){
if(same_set(u, v) && p[u][v] == 0){
works = false;
return;
}
if(p[u][v] == 0){
continue;
}
if(p[u][v] == 1 && same_set(u, v)){
continue;
}
parent[v] = u;
unite(u, v);
dfs(v);
if(!works){
return;
}
}
}
int construct(vector<vector<int> > p_){
n = p_.size();
p.resize(n, vector<int>(n));
p = p_;
adj.resize(n);
visited.resize(n, false);
parent.resize(n, -1);
e.resize(n, -1);
for(int i = 0; i < n; i++){
if(!visited[i]){
dfs(i, -1);
}
}
if(works){
vector<vector<int> > answer(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
if(parent[i] == -1) continue;
answer[i][parent[i]] = 1;
answer[parent[i]][i] = 1;
}
build(answer);
return 1;
}
else{
return 0;
}
}