제출 #285233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285233		TMJN	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	1633 ms	88440 KiB

rings

#include <bits/stdc++.h>
using namespace std;
struct UF{
	int t[1000000];
	void init(){
		for(int i=0;i<1000000;i++){
			t[i]=-1;
		}
	}
	int par(int x){
		if(t[x]<0)return x;
		return t[x]=par(t[x]);
	}
	bool uni(int x,int y){
		x=par(x);
		y=par(y);
		if(x==y)return false;
		if(t[x]<t[y]){
			t[x]+=t[y];
			t[y]=x;
		}
		else{
			t[y]+=t[x];
			t[x]=y;
		}
		return true;
	}
};

int phase,p[4];
UF uf,up[4];
int c[1000000],res;
bool b[4];
vector<int>e[1000000];


void Init(int N) {
	res=N;
	uf.init();
	for(int i=0;i<4;i++){
		up[i].init();
	}
}

void Link(int A, int B) {
	e[A].push_back(B);
	e[B].push_back(A);
	if(phase==0){
		if(e[A].size()==3){
			phase=2;
			for(int i=0;i<3;i++){
				p[i]=e[A][i];
			}
			p[3]=A;
			for(int i=0;i<4;i++){
				b[i]=true;
			}
			for(int i=0;i<4;i++){
				for(int j=0;j<1000000;j++){
					if(p[i]==j)continue;
					int c=0;
					for(int k:e[j]){
						if(p[i]==k)continue;
						c++;
						if(j<k)continue;
						if(!up[i].uni(j,k)){
							b[i]=false;
						}
					}
					if(c>=3)b[i]=false;
				}
			}
		}
		else if(e[B].size()==3){
			phase=2;
			for(int i=0;i<3;i++){
				p[i]=e[B][i];
			}
			p[3]=B;
			for(int i=0;i<4;i++){
				b[i]=true;
			}
			for(int i=0;i<4;i++){
				for(int j=0;j<1000000;j++){
					if(p[i]==j)continue;
					int c=0;
					for(int k:e[j]){
						if(p[i]==k)continue;
						c++;
						if(j<k)continue;
						if(!up[i].uni(j,k)){
							b[i]=false;
						}
					}
					if(c>=3)b[i]=false;
				}
			}
		}
		else if(!uf.uni(A,B)){
			phase=1;
			res=-uf.t[uf.par(A)];			
		}
	}
	else if(phase==1){
		if(e[A].size()==3){
			phase=2;
			for(int i=0;i<3;i++){
				p[i]=e[A][i];
			}
			p[3]=A;
			for(int i=0;i<4;i++){
				b[i]=true;
			}
			for(int i=0;i<4;i++){
				for(int j=0;j<1000000;j++){
					if(p[i]==j)continue;
					int c=0;
					for(int k:e[j]){
						if(p[i]==k)continue;
						c++;
						if(j<k)continue;
						if(!up[i].uni(j,k)){
							b[i]=false;
						}
					}
					if(c>=3)b[i]=false;
				}
			}
		}
		else if(e[B].size()==3){
			phase=2;
			for(int i=0;i<3;i++){
				p[i]=e[B][i];
			}
			p[3]=B;
			for(int i=0;i<4;i++){
				b[i]=true;
			}
			for(int i=0;i<4;i++){
				for(int j=0;j<1000000;j++){
					if(p[i]==j)continue;
					int c=0;
					for(int k:e[j]){
						if(p[i]==k)continue;
						c++;
						if(j<k)continue;
						if(!up[i].uni(j,k)){
							b[i]=false;
						}
					}
					if(c>=3)b[i]=false;
				}
			}
		}
		else if(!uf.uni(A,B)){
			phase=3;
		}
	}
	else if(phase==2){
		for(int i=0;i<4;i++){
			if(!b[i])continue;
			if(A!=p[i]&&B!=p[i]){
				if(!up[i].uni(A,B)){
					b[i]=false;
				}
				int c=0;
				for(int j:e[A]){
					if(j!=p[i])c++;
				}
				if(c>=3)b[i]=false;
				c=0;
				for(int j:e[B]){
					if(j!=p[i])c++;
				}
				if(c>=3)b[i]=false;
			}
		}
	}
}

int CountCritical() {
	if(phase==0)return res;
	if(phase==1)return res;
	if(phase==2){
		res=0;
		for(int i=0;i<4;i++){
			res+=b[i];
		}
		return res;
	}
	return 0;
}

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