Submission #4194

#	Time	Username	Problem	Language	Result	Execution time	Memory
4194		cki86201	Parachute rings (IOI12_rings)	C++98	100 / 100	1503 ms	75104 KiB

rings

int N;
const int MN = 1000010;
struct str{
	int p[MN],r[MN];
	int deg[MN];
	int px;
	bool ch;
	void init(int x){
		int i;
		for(i=0;i<N;i++){deg[i]=0,p[i]=i,r[i]=1;}
		px=x,ch=true;
	}
	int Find(int x){
		while(x!=p[x])x=p[x];
		return x;
	}
	bool Union(int x,int y){
		deg[x]++,deg[y]++;
		int a=Find(x),b=Find(y);
		if(a==b)return true;
		if(r[a]>r[b]){p[b]=a,r[a]+=r[b],r[b]=0;}
		else{p[a]=b,r[b]+=r[a],r[a]=0;}
		return false;
	}
}ring[5];
int ans;
int cnt;
bool flag_3;
bool flag_cycle;
int st[MN],en[MN<<1],next[MN<<1];
int in[MN][2];

void addedge(int s,int d,int c)
{
	next[c]=st[s];
	st[s]=c;
	en[c]=d;
}

void Init(int N_){
	ans = N = N_;
	ring[0].init(0);
}

void make_ring(int arr[])
{
	int i,j;
	for(i=0;i<4;i++){
		ring[i].init(arr[i]);
		for(j=1;j<=cnt;j++){
			if(in[j][0]==arr[i]||in[j][1]==arr[i])continue;
			if(ring[i].Union(in[j][0],in[j][1]))ring[i].ch=false;
			if(ring[i].deg[in[j][0]]>=3 || ring[i].deg[in[j][1]]>=3)ring[i].ch=false;
		}
	}
}

void Link(int A, int B){
	cnt++;
	addedge(A,B,2*cnt);
	addedge(B,A,2*cnt+1);
	in[cnt][0]=A,in[cnt][1]=B;
	if(flag_3){
		int i;
		for(i=0;i<4;i++){
			if(A!=ring[i].px && B!=ring[i].px){
				if(ring[i].Union(A,B))ring[i].ch=false;
				if(ring[i].deg[A]>=3 || ring[i].deg[B]>=3)ring[i].ch=false;
			}
		}
		return;
	}
	if(ring[0].Union(A,B)){
		if(flag_cycle)ans=0;
		else{
			int ta=ring[0].Find(A);
			ans=ring[0].r[ta];
			flag_cycle=1;
		}
	}
	if(ring[0].deg[A]>=3){
		int arr[5]={A};
		int i,tmp=1;
		for(i=st[A];i;i=next[i]){
			arr[tmp++]=en[i];
		}
		make_ring(arr);
		flag_3 = true;
	}
	else if(ring[0].deg[B]>=3){
		int arr[5]={B};
		int i,tmp=1;
		for(i=st[B];i;i=next[i]){
			arr[tmp++]=en[i];
		}
		make_ring(arr);
		flag_3 = true;
	}
}

int CountCritical(){
	if(flag_3){
		int i,ret=0;
		for(i=0;i<4;i++){
			if(ring[i].ch)ret++;
		}
		return ret;
	}
	return ans;
}

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