oj.uz

Submission #4193

# Submission time Handle Problem Language Result Execution time Memory
4193 2013-09-04T02:22:48 Z cki86201 Parachute rings (IOI12_rings) C++
0 / 100
 4000 ms 59116 KB 
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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Correct 4 ms 792 KB Output is correct
4 Incorrect 2 ms 792 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 16476 KB Output is correct
2 Correct 1959 ms 49236 KB Output is correct
3 Execution timed out 4051 ms 59116 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Correct 4 ms 792 KB Output is correct
4 Incorrect 2 ms 792 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Correct 4 ms 792 KB Output is correct
4 Incorrect 2 ms 792 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Correct 4 ms 792 KB Output is correct
4 Incorrect 2 ms 792 KB Output isn't correct
5 Halted 0 ms 0 KB -