| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1301139 | sano | 슈퍼트리 잇기 (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
// Source: https://usaco.guide/general/io
#include <iostream> // cin, cout
#include <vector> // vector
#include <string> // string
#include <set>
#include "supertrees.h"
#define vec vector
#define mod 1000000007
#define For(i,n) for(int i = 0; i < n; i++)
using namespace std;
int komponenty(vec<vec<int>>&p, vec<vec<int>>&comp, vec<int>&t){
int n = p.size();
vec<int> kde(n, -1);
for(auto i : t){
int zakl = 0;
if(kde[i] == -1){
vec<int> s;
s.push_back(i);
comp.push_back(s);
kde[i] = comp.size() - 1;
zakl = 1;
}
int poc = 0;
For(j, n){
if(p[i][j] == 0) continue;
poc++;
if(kde[j] == -1){
if(zakl){
kde[j] = kde[i];
comp[kde[i]].push_back(j);
}
else{
return 0;
}
}
if(kde[j] != kde[i]){
return 0;
}
}
if(poc != comp[kde[i]].size()) return 0;
}
}
int construct(vec<vec<int>>p){
int n = p.size();
vec<vec<int>> odp(n, vec<int>(n));
vec<vec<int>> comp;
vec<int> t;
For(i, n){
t.push_back(i);
}
int da_sa = komponenty(p, comp, t);
For(i, n){
For(j, n){
if(p[i][j] == 2) p[i][j] = 0;
}
}
For(i, comp.size()){
if(comp[i].size() == 1) continue;
vec<vec<int>> comp2;
da_sa = komponenty(p, comp2, comp[i]);
For(j, comp2.size()){
For(k, comp2[j].size()-1){
odp[comp2[k]][comp2[k+1]] = 1;
odp[comp2[k+1]][comp2[k]] = 1;
}
int p1 = comp2[j][0];
int p2 = comp2[(j+1)%(comp2.size())][0];
odp[p1][p2] = 1;
odp[p2][p1] = 1;
}
}
build(odp);
return 1;
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}*/