Submission #351190

#	Time	Username	Problem	Language	Result	Execution time	Memory
351190		juggernaut	Parachute rings (IOI12_rings)	C++14	100 / 100	1490 ms	99108 KiB

rings

//JUST UNDERSTANDED THE MAIN IDEA
#include <bits/stdc++.h>
using namespace std;
#define SZ 1234567
#define pb push_back
vector<int> adj[SZ];
int n,stage,ff[SZ],d[4],sz[SZ];
int gf(int x) {return ff[x]?ff[x]=gf(ff[x]):x;}
vector<int> ps;
void uni(int a,int b)
{
	a=gf(a),b=gf(b);
	if(a==b) ps.pb(a);
	else ff[a]=b,sz[b]+=sz[a];
}
void Init(int N_)
{
	n=N_; stage=0;
	for(int i=1;i<=n;++i) sz[i]=1;
}
struct DS
{
int u,good=1;
int ff[SZ],deg[SZ];
int gf(int x) {return ff[x]?ff[x]=gf(ff[x]):x;}
void init(int t)
{
	u=t;
}
void adde(int a,int b)
{
	if(a==u||b==u) return;
	good&=(++deg[a])<=2;
	good&=(++deg[b])<=2;
	a=gf(a),b=gf(b);
	if(a==b) good=0;
	else ff[a]=b;
}
int calc()
{return good;}
}S[4];
void rebuild(int t)
{
	for(int i=0;i<3;++i) S[i].init(adj[t][i]);
	S[3].init(t);
	for(int i=1;i<=n;++i)
		for(auto b:adj[i]) if(i<b)
			for(int k=0;k<4;++k)
				S[k].adde(i,b);
}
void Link(int x,int y) 
{
	++x,++y;
	if(!stage){
		adj[x].pb(y); adj[y].pb(x);
		uni(x,y);
		if(adj[y].size()>=3) swap(x,y);
		if(adj[x].size()>=3)
			stage=1, rebuild(x);
	}
	else{
		for(int j=0;j<4;++j)
			S[j].adde(x,y);
	}
}
int CountCritical(){
	if(!stage)
	{
		if(ps.size()>=2) return 0;
		if(ps.size()==0) return n;
		return sz[gf(ps[0])];
	}
	else
		return S[0].calc()+S[1].calc()+S[2].calc()+S[3].calc();
}

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