Submission #137491

#	Time	Username	Problem	Language	Result	Execution time	Memory
137491		mohammedehab2002	Parachute rings (IOI12_rings)	C++11	100 / 100	2690 ms	80592 KiB

rings

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > e;
struct graph
{
	int v,par[1000005],deg[1000005],sz[1000005],cyc,csz;
	pair<int,int> mx;
	graph()
	{
		v=-1;
		cyc=0;
		mx={0,0};
		for (int i=0;i<1e6;i++)
		{
			par[i]=i;
			deg[i]=0;
			sz[i]=1;
		}
	}
	int find(int x)
	{
		if (par[x]!=x)
		par[x]=find(par[x]);
		return par[x];
	}
	void Union(int x,int y)
	{
		deg[x]++;
		deg[y]++;
		mx=max(mx,{deg[x],x});
		mx=max(mx,{deg[y],y});
		x=find(x);
		y=find(y);
		if (x==y)
		{
			cyc++;
			csz=sz[x];
		}
		else
		{
			par[x]=y;
			sz[y]+=sz[x];
		}
	}
};
int n;
graph g[5];
bool f;
void Init(int nn)
{
	n=nn;
}
void Link(int a,int b)
{
	e.push_back({a,b});
	if (!f)
	{
		g[0].Union(a,b);
		if (g[0].mx.first==3)
		{
			f=1;
			vector<int> cur({g[0].mx.second});
			for (auto p:e)
			{
				if (p.first==cur[0] || p.second==cur[0])
				cur.push_back(p.first^p.second^cur[0]);
			}
			for (int i=0;i<4;i++)
			{
				g[i+1].v=cur[i];
				for (auto p:e)
				{
					if (p.first!=cur[i] && p.second!=cur[i])
					g[i+1].Union(p.first,p.second);
				}
			}
		}
	}
	else
	{
		for (int i=1;i<5;i++)
		{
			if (g[i].v!=a && g[i].v!=b)
			g[i].Union(a,b);
		}
	}
}
int CountCritical()
{
	if (!f)
	{
		if (!g[0].cyc)
		return n;
		if (g[0].cyc>1)
		return 0;
		return g[0].csz;
	}
	int ans=0;
	for (int i=1;i<5;i++)
	ans+=(g[i].mx.first<=2 && !g[i].cyc);
	return ans;
}

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