| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1356751 | cowkim | 슈퍼트리 잇기 (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
struct UF{
vector<int> p;
vector<int> sz;
UF(int n) : p(n,-1), sz(n,1){}
int find(int x){
return p[x] == -1 ? x : p[x] = find(p[x]);
}
bool combine(int a, int b){
a = find(a);
b = find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a,b);
p[b] = a;
sz[a] += sz[b];
return true;
}
int same(int a, int b){
return find(a) == find(b);
}
};
int construct(vector<vector<int>> p){
int n = p.size();
UF uf(p.size());
vector<pair<int,int>> edges;
for(int i = 0; i< n; i++){
for(int j = 0; j< n; j++){
if(i == j) continue;
if(p[i][j] == 1){
if(uf.combine(i,j)) edges.push_back({i,j});
}
}
}
for(int i = 0; i< n; i++){
for(int j = 0; j< n; j++){
if(uf.same(i,j) && p[i][j] != 1) return 0;
}
}
vector<vector<int>> cycles;
for(int i = 0; i< n; i++){
if(uf.p[i] != -1) continue;
bool found = false;
for(auto& cycle : cycles){
if(p[cycle[0]][i] == 2){
cycle.push_back(i);
found = true;
break;
}
}
if(!found) cycles.push_back({i});
}
for(int cycle = 0; cycle < cycles.size(); cycle++){
for(int cycle2 = cycle +1; cycle2 < cycles.size(); cycle2++){
for(auto node : cycles[cycle]){
for(auto node2 : cycles[cycle2]){
if(p[node][node2] == 2) return 0;
}
}
}
}
for(auto& cycle : cycles){
for(auto& node : cycle){
for(auto& node2 : cycle){
if(node == node2) continue;
if(p[node][node2] != 2) return false;
}
}
}
for(auto& cycle : cycles){
if(cycle.size() == 2) return false;
if(cycle.size() == 1) continue;
for(int i = 0; i< cycle.size()-1; i++){
edges.push_back({cycle[i],cycle[i+1]});
}
edges.push_back({cycle[0],cycle[cycle.size()-1]});
}
//kolla om alla barn är 2 eller 0
vector<vector<int>> b(n,vector<int>(n,0));
for(auto edge : edges){
b[edge.first][edge.second] = 1;
b[edge.second][edge.first] = 1;
}
build(b);
return 1;
}
// void build(vector<vector<int>> b){
// }
// int main(){
// return 0;
// }