Submission #59237

#	Time	Username	Problem	Language	Result	Execution time	Memory
59237		TadijaSebez	Parachute rings (IOI12_rings)	C++11	100 / 100	3522 ms	82820 KiB

rings

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
const int N=1000050;
int n;
struct DSU
{
	int p[N],c[N],deg[N];
	int cyc,my,sz;
	bool ok;
	DSU(){}
	void init(int x)
	{
		my=x;cyc=sz=0;ok=1;
		for(int i=0;i<n;i++) p[i]=i,c[i]=1,deg[i]=0;
	}
	int Find(int x){ return x==p[x]?x:p[x]=Find(p[x]);}
	void Union(int x, int y)
	{
		if(x==my || y==my) return;
		deg[x]++;deg[y]++;
		if(deg[x]>2 || deg[y]>2) ok=0;
		x=Find(x);y=Find(y);
		if(x==y){ cyc++,sz=c[x],ok=0;return;}
		if(c[y]>c[x])
		{
			p[x]=y;
			c[y]+=c[x];
		}
		else
		{
			p[y]=x;
			c[x]+=c[y];
		}
	}
} Base,Try[4];
int E[N][3];
int esz;
pair<int,int> edges[N];
int deg[N],sz;
bool mod;
void Init(int m){ n=m;Base.init(-1);}
void Push()
{
	for(int i=0;i<esz;i++)
	{
		for(int j=0;j<sz;j++)
		{
			Try[j].Union(edges[i].first,edges[i].second);
		}
	}
}
void Link(int a, int b)
{
	if(deg[a]<3) E[a][deg[a]]=b;
	deg[a]++;
	if(deg[b]<3) E[b][deg[b]]=a;
	deg[b]++;
	Base.Union(a,b);
	edges[esz++]=mp(a,b);
	if(mod)
	{
		for(int i=0;i<sz;i++) Try[i].Union(a,b);
		return;
	}
	if(deg[a]>2)
	{
		sz=4;
		Try[0].init(a);
		for(int i=0;i<3;i++) Try[i+1].init(E[a][i]);
		Push();
		mod=1;
		return;
	}
	if(deg[b]>2)
	{
		sz=4;
		Try[0].init(b);
		for(int i=0;i<3;i++) Try[i+1].init(E[b][i]);
		Push();
		mod=1;
		return;
	}
}
int CountCritical()
{
	if(mod)
	{
		int ans=0;
		for(int i=0;i<sz;i++) if(Try[i].ok) ans++;
		return ans;
	}
	if(Base.cyc>1) return 0;
	if(Base.cyc==1) return Base.sz;
	return n;
}

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