# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
487887 | ala2 | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <vector>
#include<iostream>
using namespace std;
int pa[1001000];
int sz[1001000];
int root(int x)
{
while(x!=pa[x])
{
pa[x]=pa[pa[x]];
x=pa[x];
}
return x;
}
void unit(int x,int y)
{
x=root(x);
y=root(y);
if(x==y)
return ;
if(sz[x]>sz[y])
{
sz[x]+=sz[y];
pa[y]=x;
}
else
{
sz[y]+=sz[x];
pa[x]=y;
}
}
vector<int>v[1010];
int vi[1010];
int vis[5][1010][1010];
int construct(vector<vector<int>> p) {
int n = p.size();
int bb=0;
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
answer.push_back(row);
}
for(int i=0;i<n;i++)
{
pa[i]=i;
sz[i]=1;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(p[i][j]==1)
{
unit(i,j);
}
}
}
for(int i=0;i<n;i++)
{
v[root(i)].push_back(i);
}
for(int i=0;i<n;i++)
{
if(i!=root(i))
continue;
if(v[i].size()==1)
{
continue;
}
for(int j=0;j<v[i].size()-1;j++)
{
int x=v[i][j];
int y=v[i][j+1];
answer[x][y]=1;
answer[y][x]=1;
}
}
for(int i=0;i<n;i++)
{
if(i!=root(i))
continue;
int tow=0;
vector<int>r;
r.push_back(i);
vi[root(i)]=1;
for(int j=0;j<n;j++)
{
if(p[i][j]>=2&&!vi[root(j)])
{
if(p[i][j]==2)
tow=2;
else tow=3,three=1;
r.push_back(root(j));
vi[root(j)]=1;
}
}
if(tow&&three){
bb=1;
break;
}
// cout<<" "<<r.size()<<endl;
if(r.size()==1)
continue;
if(r.size()==2&&tow==2){
bb=1;
break;
}
if(r.size()<=3&&tow==3){
bb=1;
break;
}
for(int k=0;k<r.size()-1;k++)
{
int x=r[k];
int y=r[k+1];
answer[x][y]=1;
answer[y][x]=1;
}
int ss=r.size()-1;
answer[r[ss]][r[0]]=1;
answer[r[0]][r[ss]]=1;
if(tow>2){
answer[r[0]][r[2]]=1;
answer[r[2]][r[0]]=1;
}
for(int ii=0;ii<r.size();ii++)
{
for(int jj=0;jj<r.size();jj++)
{
if(ii==jj)
continue;
vis[tow][r[ii]][r[jj]]=1;
vis[tow][r[jj]][r[ii]]=1;
}
}
}
for(int i=0;i<n;i++)
{
answer[i][i]=0;
for(int j=0;j<n;j++)
{
if(i==j)
continue;
// cout<<vis[i][j]<<" ";
if(p[i][j]==2&&vis[3][root(i)][root(j)])
bb=1;
if(p[i][j]==3&&vis[2][root(i)][root(j)])
bb=1;
if(p[i][j]>=2&&!vis[p[i][j]][root(i)][root(j)])
bb=1;
if(p[i][j]<2&&vis[p[i][j]][root(i)][root(j)])
bb=1;
if(p[i][j]==1&&root(i)!=root(j))
bb=1;
if(root(i)==root(j)&&p[i][j]!=1)
bb=1;
if(p[i][j]==0&&vis[3][root(i)][root(j)])
bb=1;
if(p[i][j]==0&&vis[2][root(i)][root(j)])
bb=1;
}
}
if(bb)
return 0;
else
{
build(answer);
return 1;
}
}