Submission #16385

#	Time	Username	Problem	Language	Result	Execution time	Memory
16385		comet	Parachute rings (IOI12_rings)	C++98	20 / 100	1754 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;
struct graph{
	vector<int> p,r;
	mat path;
	void init(int n){
		p.resize(n);
		r.resize(n,0);
		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;
		if(r[x]>r[y])swap(x,y);
		p[x]=y;
		if(r[x]==r[y])r[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;
		}
	}
}

Compilation message (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<A.path[v].size();i++){
               ~^~~~~~~~~~~~~~~~~
rings.cpp: In function 'void make_graph(int, int)':
rings.cpp:91: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:115:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<A.path[x].size();i++)
                ~^~~~~~~~~~~~~~~~~
rings.cpp:145:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<A.path[x].size();i++){
                ~^~~~~~~~~~~~~~~~~

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