Submission #287813

#	Time	Username	Problem	Language	Result	Execution time	Memory
287813		tinjyu	Parachute rings (IOI12_rings)	C++14	0 / 100	860 ms	65784 KiB

rings

#include <iostream>
using namespace std;
int n,f[1000005][4],count[1000005][4],st[1000005][4],en[1000005][4],deg[1000005],tree[4],circle[4],cnt,a[1000005],b[1000005],c;

void Init(int N_) {

  n = N_;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=3;j++)
		{
			f[i][j]=i;
			st[i][j]=i;
			en[i][j]=i;
			count[i][j]=1;
		}
	}
}
int find(int x,int a)
{
	if(f[x][a]==x)return x;
	else return f[x][a]=find(f[x][a],a);
}
int link(int x,int y,int a)
{
	int fx=find(x,a),fy=find(y,a);
	if(fx==fy)
	{
		if((st[fx][a]==x && en[fx][a]==y) || (st[fx][a]==y && en[fx][a]==x))
		{
			if(circle[a]!=0)circle[a]=-1;
			else circle[a]=count[fx][a];
		}
		else tree[a]=1;
		return 0;
	}
	if((st[fx][a]!=x && en[fx][a]!=x) || (st[fy][a]!=y && en[fy][a]!=y))
	{
		tree[a]=1;
		return 0;
	}
	f[fx][a]=fy;
	count[fy][a]+=count[fx][a];
	int ns,ne;
	if(st[fy][a]==y)ns=en[fy][a];
	else ns=st[fy][a];
	if(st[fx][a]==x)ne=en[fx][a];
	else ne=st[fx][a];
	st[fy][a]=ns;
	en[fy][a]=ne;
	return 0;
}
void Link(int A, int B) {
	cnt++;
	a[cnt]=A;
	b[cnt]=B;
	deg[A]++;
	deg[B]++;
	if((deg[A]==3 || deg[B]==3) && c==0)
	{
		c=1;
		long long int w,x=-1,y=-1,z=-1;
		if(deg[A]==3)w=A;
		else w=B;
		for(int i=1;i<=cnt;i++)
		{
			if(a[i]==w)
			{
				if(x==-1)x=b[i];
				else if(y==-1)y=b[i];
				else z=b[i];
			}
			else if(b[i]==w)
			{
				if(x==-1)x=a[i];
				else if(y==-1)y=a[i];
				else z=a[i];			
			}
		}
		for(int j=0;j<=3;j++)
		{
			tree[j]=0;
			circle[j]=0;
			for(int i=0;i<n;i++)
			{
				f[i][j]=i;
				count[i][j]=1;
				st[i][j]=i;
				en[i][j]=i;
			}
			for(int i=1;i<=cnt;i++)
			{
				if(j==0 && (a[i]==w || b[i]==w))continue;
				if(j==1 && (a[i]==x || b[i]==x))continue;
				if(j==2 && (a[i]==y || b[i]==y))continue;
				if(j==3 && (a[i]==z || b[i]==z))continue;
				link(a[i],b[i],j);
			}
		}
	}
	else if(c==1)
	{
		for(int i=0;i<=3;i++)link(a[cnt],b[cnt],i);
	}
	else link(a[cnt],b[cnt],0);
}

int CountCritical() {
	if(c==1)
	{
		int ans=0;
		if(circle[0]==0 && tree[0]==0)ans++;
		if(circle[1]==0 && tree[1]==0)ans++;
		if(circle[2]==0 && tree[2]==0)ans++;
		if(circle[3]==0 && tree[3]==0)ans++;
		return ans;
	}
	if(circle[0]==0)return n;
	if(circle[0]==-1)return 0;
	return circle[0];
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31