| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1214796 | Math4Life2020 | 슈퍼트리 잇기 (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include "build.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
int construct(vector<vector<int>> p) {
ll N = p.size();
vector<vector<int>> cstr(N,vector<ll>(N,0)); //construction
for (ll i=0;i<N;i++) {
for (ll j=0;j<N;j++) {
if (p[i][j]==3) {
return 0;
}
}
}
vector<bool> found(N,false);
vector<bool> found2(N,false);
for (int i=0;i<N;i++) {
if (!found[i]) {
vector<int> vin,vout;
for (int j=0;j<N;j++) {
if (p[i][j]!=0) {
vin.push_back(j);
found[j]=1;
} else {
vout.push_back(j);
}
}
for (int a: vin) {
for (int b: vin) {
if (p[a][b]==0) {
return 0;
}
}
}
for (int a: vin) {
for (int b: vout) {
if (p[a][b]!=0) {
return 0;
}
}
}
vector<vector<int>> vclq; //cliques
for (int x: vin) {
if (!found2[x]) {
vector<int> clqt;
for (int y: vin) {
if (p[x][y]==1) {
if (found2[y]) {
return 0;
}
found2[y]=1;
clqt.push_back(y);
}
}
vclq.push_back(clqt);
}
}
for (auto v0: vclq) {
ll m = v0.size();
for (ll i=1;i<m;i++) {
cstr[v0[0]][v0[i]]=1;
cstr[v0[i]][v0[0]]=1;
}
for (ll a: v0) {
for (ll b: v0) {
if (p[a][b]!=1) {
return 0;
}
}
}
}
ll sz = vclq.size();
for (ll i=0;i<sz;i++) {
cstr[vclq[i][0]][vclq[(i+1)%sz][0]]=1;
cstr[vclq[(i+1)%sz][0]][vclq[i][0]]=1;
}
for (ll i=0;i<sz;i++) {
for (ll j=(i+1);j<sz;j++) {
for (ll a: vclq[i]) {
for (ll b: vclq[j]) {
if (p[a][b]!=2) {
//cout << "a,b="<<a<<","<<b<<"\n";
return 0;
}
}
}
}
}
}
}
build(cstr);
return 1;
}