Submission #301697

#	Time	Username	Problem	Language	Result	Execution time	Memory
301697		tinjyu	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	290 ms	26276 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>
using namespace std;
int f[100005],map[1005][1005],pre[10005],tmp[10005],circle[100005],ccnt,tag[10005],tmp2[100005],tag2[100005];
int find(int x)
{
if(f[x]==x)return x;
else return f[x]=find(f[x]);
}
int construct(std::vector<std::vector<int>> p) {

int n = p[0].size();
std::vector<std::vector<int>> answer;
for(int i=0;i<n;i++)f[i]=i;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(p[i][j]==3)return 0;
if(i==j)continue;
int fx=find(i),fy=find(j);
if(p[i][j]==0 && fx==fy)return 0;

if(p[i][j]!=0)
{
f[fx]=fy;
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int fx=find(i),fy=find(j);
if(p[i][j]==0 && fx==fy)return 0;
}
}
for(int i=0;i<n;i++)
{
pre[i]=-1;
}
for(int i=0;i<n;i++)
{
int cnt=0;
for(int j=0;j<n;j++)
{
if(find(j)==i)
{
cnt++;
tmp[cnt]=j;
}
}
if(cnt==0)continue;
//cout<<i<<endl;
//for(int j=1;j<=cnt;j++)cout<<tmp[j]<<" ";
//cout<<endl;
ccnt=0;
for(int j=0;j<n;j++)tag2[j]=0;
for(int j=1;j<=cnt;j++)//in one set
{
if(tag[tmp[j]]==1)continue;
int x=tmp[j],cnt2=0;
tag[x]=1;
tmp2[0]=x;
tag2[x]=x;
for(int k=1;k<=cnt;k++)
{
int y=tmp[k];
if(x==y)continue;
if(p[x][y]==1)
{
cnt2++;
tmp2[cnt2]=y;
tag2[y]=x;
tag[y]=1;
}
}
for(int k=1;k<=cnt2;k++)
{
int y=tmp2[k];
//cout<<y<<endl;
int count=0;
for(int l=1;l<=cnt;l++)
{
int z=tmp[l];
if(y==z)continue;
if(p[y][z]==1)
{
//cout<<z<<" ";
if(tag2[z]!=x)return 0;
count++;
}
}
//cout<<count<<endl;
if(count!=cnt2)return 0;
}
for(int k=0;k<cnt2;k++)
{
map[tmp2[k]][tmp2[k+1]]=1;
map[tmp2[k+1]][tmp2[k]]=1;
}
ccnt++;
//cout<<ccnt<<endl;
circle[ccnt]=x;
}
if(ccnt==1)continue;
if(ccnt==2)return 0;
for(int i=1;i<ccnt;i++)
{
map[circle[i]][circle[i+1]]=1;
map[circle[i+1]][circle[i]]=1;
}
map[circle[1]][circle[ccnt]]=1;
map[circle[ccnt]][circle[1]]=1;
}
for(int i=0;i<n;i++)
{
vector<int> tmp(n);
for(int j=0;j<n;j++)tmp[j]=map[i][j];
answer.push_back(tmp);
}
build(answer);
return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4