제출 #16388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16388		comet	낙하산 고리들 (IOI12_rings)	C++98	20 / 100	2669 ms	263168 KiB

rings

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pb push_back
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
int N,mode;
vector<int> p[5];
mat path[5];

void init(int n,int k){
	p[k].resize(n);
	path[k].assign(n,vec());
	for(int i=0;i<n;i++)p[k][i]=i;
}

int find(int x,int k){
	if(p[k][x]==x)return x;
	return p[k][x]=find(p[k][x],k);
}

bool merge(int x,int y,int k){
	x=find(x,k),y=find(y,k);
	if(x==y)return 0;
	p[k][x]=y;
	return 1;
}

void finish(int k){
	p[k].clear();
	path[k].clear();
}

bool CircleChk[1000000],chk[4];
int cnt,Ex[4];

void Init(int n){
	N=n;
	init(n,4);
}

int CountCritical(){
	// Base
	if(mode==0){
		return N;
	}

	// Circle
	else if(mode==1){
		return cnt;
	}

	// Divided
	else if(mode==2){
		cnt=0;
		for(int k=0;k<4;k++)if(!chk[k])cnt++;
		if(cnt==0)mode=-1;
		return cnt;
	}

	// End
	else{
		return 0;
	}
}

void CircleBfs(int v){
	queue<int> Q;
	Q.push(v);
	CircleChk[v]=1;
	while(!Q.empty()){
		v=Q.front();
		cnt++;
		Q.pop();
		for(int i=0;i<path[4][v].size();i++){
          	int u=path[4][v][i];
			if(!CircleChk[u]){
				Q.push(u);
				CircleChk[u]=1;
			}
		}
	}
}

void make_graph(int x,int k){
	init(N,k);
	Ex[k]=x;
	for(int i=0;i<N;i++){
		if(x==i)continue;
		for(int t=0;t<path[4][i].size();t++){
			int j=path[4][i][t];
			if(j==x)continue;
			path[k][i].pb(j);
			merge(i,j,k);
		}
		if(path[k][i].size()>2){
			chk[k]=1;
			finish(k);
			return;
		}
	}
}

void Link(int x,int y){
	//End
	if(mode<0)return;

	// Base
	if(mode==0){
		path[4][x].pb(y);
		path[4][y].pb(x);
		if(path[4][x].size()<path[4][y].size())swap(x,y);
		if(path[4][x].size()>2){
			mode=2;
			for(int i=0;i<3;i++)
				make_graph(path[4][x][i],i);
			make_graph(x,3);
			finish(4);
			return;
		}

		if(!merge(x,y,4)){
			cnt=0;
			mode=1;
			CircleBfs(x);
		}
	}


	// Circle
	else if(mode==1){
		path[4][x].pb(y);
		path[4][y].pb(x);
		if(!merge(x,y,4)){
			mode=-1;
			return;
		}
		if(path[4][x].size()<path[4][y].size())swap(x,y);
		if(path[4][x].size()>2){
			if(CircleChk[x]==0&&CircleChk[y]==0){
				mode=-1;
				return;
			}
			mode=2;
			for(int i=0;i<path[4][x].size();i++){
				if(!CircleChk[path[4][x][i]]){
					chk[i]=1;
					continue;
				}
				make_graph(path[4][x][i],i);
			}
			make_graph(x,3);
			finish(4);
			return;
		}
	}

	// Divided
	else if(mode==2){
		for(int k=0;k<4;k++){
			if(chk[k])continue;
			if(Ex[k]==x||Ex[k]==y)continue;
			path[k][x].pb(y);
			path[k][y].pb(x);
			if(!merge(x,y,k))chk[k]=1;
			if(path[k][x].size()<path[k][y].size())swap(x,y);
			if(path[k][x].size()>2){
				chk[k]=1;
				finish(k);
			}
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

rings.cpp: In function 'void CircleBfs(int)':
rings.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<path[4][v].size();i++){
               ~^~~~~~~~~~~~~~~~~~
rings.cpp: In function 'void make_graph(int, int)':
rings.cpp:92:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int t=0;t<path[4][i].size();t++){
               ~^~~~~~~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:147:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<path[4][x].size();i++){
                ~^~~~~~~~~~~~~~~~~~

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