Submission #4193

#	Time	Username	Problem	Language	Result	Execution time	Memory
4193		cki86201	Parachute rings (IOI12_rings)	C++98	0 / 100	4051 ms	59116 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){
		int r=x;
		while(p[r]!=r)r=p[r];
		p[x]=r;
		while(x!=r){x=p[x];p[x]=r;}
		return p[x]=r;
	}
	bool Union(int x,int y){
		deg[x]++,deg[y]++;
		int a=Find(x),b=Find(y);
		if(r[a]>r[b]){p[b]=a,r[b]+=r[a],r[a]=0;}
		else{p[a]=b,r[a]+=r[b],r[b]=0;}
		return a==b;
	}
}ring[5];
int ans;
int cnt;
bool flag_3;
int st[MN],en[MN],next[MN];

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,k;
	for(i=0;i<4;i++){
		ring[i].init(arr[i]);
		for(j=0;j<N;j++){
			for(k=st[j];k;k=next[k]){
				if(k&1)continue;
				if(j!=arr[i] && en[k]!=arr[i]){
					ring[i].Union(j,en[k]);
				}
			}
		}
	}
}

void Link(int A, int B){
	cnt++;
	addedge(A,B,2*cnt);
	addedge(B,A,2*cnt+1);
	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)){
		int ta=ring[0].Find(A),tb=ring[0].Find(B);
		ans=ring[0].r[ta]+ring[0].r[tb];
	}
	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: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31