답안 #16383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16383	2015-08-22T04:29:05 Z	comet	낙하산 고리들 (IOI12_rings)	C++	컴파일 오류	0 ms	0 KB

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;
struct graph{
	vector<int> p;
	mat path;
	void init(int n){
		p.resize(n);
		path.assign(n,vec());
		for(int i=0;i<n;i++)p[i]=i;
	}
	int find(int x){
		if(p[x]==x)return x;
		return p[x]=find(p[x]);
	}
	bool merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return 0;
		p[x]=y;
		return 1;
	}
	void finish(){
		path.clear();
	}
}A,z[4];
bool CircleChk[1000000],chk[4];
int cnt,Ex[4];

void Init(int n){
	N=n;
	A.init(n);
	for(int i=0;i<4;i++)z[i].init(n);
}

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<A.path[v].size();i++){
          	int u=A.path[v][i];
			if(!CircleChk[u]){
				Q.push(u);
				CircleChk[u]=1;
			}
		}
	}
}

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

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

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

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


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

int main(){
	int n,L,x,y;
	scanf("%d%d\n",&n,&L);
	Init(n);
	for(int i=0;i<L;i++){
		scanf("%d",&x);
		if(x<0){
			printf("%d\n",CountCritical());
		}
		else{
			scanf("%d",&y);
			Link(x,y);
		}
	}
}

Compilation message

rings.cpp: In function 'void CircleBfs(int)':
rings.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<A.path[v].size();i++){
               ~^~~~~~~~~~~~~~~~~
rings.cpp: In function 'void make_graph(int, int)':
rings.cpp:88:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int t=0;t<A.path[i].size();t++){
               ~^~~~~~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<A.path[x].size();i++)
                ~^~~~~~~~~~~~~~~~~
rings.cpp:142:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<A.path[x].size();i++){
                ~^~~~~~~~~~~~~~~~~
rings.cpp: In function 'int main()':
rings.cpp:171:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d\n",&n,&L);
  ~~~~~^~~~~~~~~~~~~~~~
rings.cpp:174:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
rings.cpp:179:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&y);
    ~~~~~^~~~~~~~~
/tmp/ccgnGJ10.o: In function `main':
rings.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccK3SYBJ.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status