Submission #986343

#	Time	Username	Problem	Language	Result	Execution time	Memory
986343		Pyqe	Parachute rings (IOI12_rings)	C++17	100 / 100	1678 ms	164104 KiB

rings

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,m=0,d=0,nn=1,dg[5][1000069],dsu[5][1000069],e[5]={-1},c[5],c2[5],z;
pair<long long,long long> ed[1000069];
vector<long long> al[1000069];
bitset<1000069> vtd;
bool r0=0;

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

void bd(long long x)
{
	long long i,ii,k,l;
	
	e[nn]=x;
	c[nn]=0;
	c2[nn]=0;
	for(i=1;i<=n;i++)
	{
		dg[nn][i]=0;
		dsu[nn][i]=i;
	}
	for(i=1;i<m;i++)
	{
		k=ed[i].fr;
		l=ed[i].sc;
		if(k!=x&&l!=x)
		{
			for(ii=0;ii<2;ii++)
			{
				dg[nn][k]++;
				c[nn]+=dg[nn][k]>=3;
				swap(k,l);
			}
			c2[nn]+=fd(nn,k)==fd(nn,l);
			dsu[nn][fd(nn,l)]=fd(nn,k);
		}
	}
	nn++;
}

void dfs(long long x,long long y)
{
	long long i,sz=al[x].size(),l;
	
	vtd[x]=1;
	if(x==y)
	{
		d++;
		r0=1;
		return;
	}
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		if(!vtd[l])
		{
			dfs(l,y);
			if(r0)
			{
				d++;
				return;
			}
		}
	}
}

void Init(int on)
{
	long long i;
	
	n=on;
	z=n;
	for(i=1;i<=n;i++)
	{
		dsu[0][i]=i;
	}
}

void Link(int x,int y)
{
	long long i,ii;
	
	x++;
	y++;
	m++;
	ed[m]={x,y};
	z=0;
	for(i=0;i<nn;i++)
	{
		if(x!=e[i]&&y!=e[i])
		{
			for(ii=0;ii<2;ii++)
			{
				dg[i][x]++;
				if(dg[i][x]>=3)
				{
					c[i]++;
					if(!i&&dg[0][e[1]]<=3)
					{
						if(dg[i][x]==3)
						{
							if(nn<5)
							{
								bd(x);
								bd(y);
								bd(al[x][0]);
								bd(al[x][1]);
							}
						}
						else
						{
							nn=1;
							bd(x);
						}
					}
				}
				swap(x,y);
			}
			if(fd(i,x)==fd(i,y))
			{
				c2[i]++;
				if(!i&&c2[i]==1)
				{
					dfs(x,y);
				}
			}
			dsu[i][fd(i,y)]=fd(i,x);
			if(!i)
			{
				al[x].push_back(y);
				al[y].push_back(x);
			}
		}
		if(!c[i])
		{
			if(!i)
			{
				if(!c2[i])
				{
					z+=n;
				}
				else if(c2[i]==1)
				{
					z+=d;
				}
			}
			else
			{
				z+=!c2[i];
			}
		}
	}
}

int CountCritical()
{
	return z;
}

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