Submission #986409

#	Time	Username	Problem	Language	Result	Execution time	Memory
986409		Pyqe	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	174 ms	24248 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

long long n,dsu[2][1069];
vector<long long> vl[1069];

long long fd(long long xx,long long x)
{
	if(dsu[xx][x]!=x)
	{
		dsu[xx][x]=fd(xx,dsu[xx][x]);
	}
	return dsu[xx][x];
}

int construct(vector<vector<int>> a)
{
	long long i,j,ii,k,l,sz;
	vector<int> v;
	vector<vector<int>> sq;
	
	n=a.size();
	for(i=0;i<n;i++)
	{
		for(ii=0;ii<2;ii++)
		{
			dsu[ii][i]=i;
		}
		sq.push_back(v);
		for(j=0;j<n;j++)
		{
			sq[i].push_back(0);
		}
	}
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(a[i][j]==1&&fd(0,i)!=fd(0,j))
			{
				sq[i][j]=1;
				sq[j][i]=1;
				for(ii=0;ii<2;ii++)
				{
					dsu[ii][fd(ii,j)]=fd(ii,i);
				}
			}
		}
	}
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(a[i][j]==2)
			{
				dsu[1][fd(1,j)]=fd(1,i);
			}
		}
	}
	for(i=0;i<n;i++)
	{
		if(fd(0,i)==i)
		{
			vl[fd(1,i)].push_back(i);
		}
	}
	for(i=0;i<n;i++)
	{
		sz=vl[i].size();
		if(sz==2)
		{
			return 0;
		}
		for(j=0;j<sz;j++)
		{
			k=vl[i][j];
			if(j)
			{
				sq[k][l]=1;
				sq[l][k]=1;
			}
			l=k;
		}
		if(sz>=3)
		{
			sq[l][vl[i][0]]=1;
			sq[vl[i][0]][l]=1;
		}
	}
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if((!a[i][j]&&fd(1,i)==fd(1,j))||(a[i][j]==2&&fd(0,i)==fd(0,j))||a[i][j]==3)
			{
				return 0;
			}
		}
	}
	build(sq);
	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