| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 315860 | juggernaut | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"supertrees.h"
#include<bits/stdc++.h>
#ifdef EVAL
#else
#include"grader.cpp"
#endif
using namespace std;
int par[1005],pr[1005];
bool vis[1005];
vector<int>st[1005],comp;
vector<vector<int>>P,v;
int fin(int v){
return v==par[v]?v:par[v]=fin(par[v]);
}
void unite(int x,int y){
x=fin(x);
y=fin(y);
if(x!=y){
if(st[x].size()<st[y].size())swap(x,y);
st[x].insert(st[x].end(),st[y].begin(),st[y].end());
st[y].clear();
par[y]=x;
}
}
void dfs(int vv){
comp.push_back(vv);
vis[vv]=1;
pr[vv]=1;
for(int i=0;i<n;i++)if(!vis[i]&&P[vv][i]==1)vis[i]=1,pr[i]=vv,v[vv][i]=v[i][vv]=1;
for(int i=0;i<n;i++)if(!vis[i]&&P[vv][i]==2)dfs(i);
}
int construct(vector<vector<int>>p){
P=p;
int n=p.size(),i,j;
v.resize(n);
fill(v.begin(),v.end(),vector<int>(n,0));
for(i=0;i<n;i++)par[i]=i,st[i].push_back(i);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(p[i][j]==3)return 0;
if(p[i][j])unite(i,j);
}
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if((!p[i][j]&&fin(i)==fin(j))||(p[i][j]&&fin(i)!=fin(j)))return 0;
for(i=0;i<n;i++)
if(!st[i].empty()){
comp.clear();
dfs(st[i][0]);
for(int j=1;j<comp.size();j++)v[comp[j]][comp[j-1]]=v[comp[j-1]][comp[j]]=1;
if(comp.size()!=1)v[comp[0]][comp.back()]=v[comp.back()][comp[0]]=1;
if(comp.size()==2)return 0;
for(int vv:st[i])
for(int to:st[vv])if(pr[vv]==pr[to]&&P[vv][to]!=1)return 0;
}
build(v);
return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/