Submission #124810

#	Time	Username	Problem	Language	Result	Execution time	Memory
124810		nxteru	Parachute rings (IOI12_rings)	C++14	100 / 100	1451 ms	104176 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
int n,par[3][1000005],v1=-1,v2=-1,ins,rps,ino[1000005],rpo[1000005],in[1000005],ts,ans,nx[1000005],vis[1000005],fr=-1,tr[1000005],trs;
bool zr,rpt,rpt2,ok1,ok2;
vector<int>g[1000005];
int find(int q,int x){
	if(par[q][x]==x)return x;
	return par[q][x]=find(q,par[q][x]);
}
bool same(int q,int x,int y){
	return find(q,x)==find(q,y);
}
int unit(int q,int x,int y){
	par[q][find(q,y)]=find(q,x);
}
void Init(int N){
	n=N;
	for(int i=0;i<n;i++)par[0][i]=i,par[1][i]=i,par[2][i]=i,nx[i]=-1;
	ans=n;
}
void check(int v){
	if(ino[v]==ins&&rpo[v]==rps)ans++;
}
void up(int v){
	in[v]++;
	if(in[v]==3){
		trs++;
		tr[v]++;
		for(int i=0;i<g[v].size();i++)tr[g[v][i]]++;
		ans=0;
		ins++;
		if(fr!=-1){
			if(tr[fr]==trs){
				ino[fr]=ins;
				check(fr);
			}
		}else{
			if(tr[v]==trs)ino[v]=ins;
			check(v);
			for(int i=0;i<g[v].size();i++){
				int u=g[v][i];
				if(tr[u]==trs)ino[u]=ins;
				check(u);
			}
		}
	}else if(in[v]==4){
		if(fr==-1){
			fr=v;
			if(tr[v]==trs){
				ins++;
				ino[v]=ins;
				ans=0;
				check(v);
			}else zr=true;
		}else zr=true;
	}
}
void dfs1(int v,int p){
	nx[v]=p;
	for(int i=0;i<g[v].size();i++){
		if(g[v][i]!=p)dfs1(g[v][i],v);
	}
}
void Link(int a,int b){
	if(zr)return;
	if(rpt2){
		ans=0;
		rps++;
		if(same(1,a,b))ok1=false;
		if(same(2,a,b))ok2=false;
		if(v1!=a&&v1!=b)unit(1,a,b);
		if(v2!=a&&v2!=b)unit(2,a,b);
		if(ok1)rpo[v1]=rps;
		if(ok2)rpo[v2]=rps;
		check(v1);
		if(v2!=-1)check(v2);
	}else if(!same(0,a,b)){
		unit(0,a,b);
		if(nx[b]==-1)swap(a,b);
		if(nx[a]==-1&&nx[b]!=-1)dfs1(a,b);
	}else{
		if(!rpt){
			rpt=true;
			dfs1(a,a);
			ans=0;
			rps++;
			int v=b;
			while(1){
				vis[v]=rps;
				rpo[v]=rps;
				check(v);
				if(v==a)break;
				v=nx[v];
			}
		}else{
			rpt2=true;
			if(nx[a]==-1||nx[b]==-1)zr=true;
			else{
				ans=0;
				rps++;
				int v=a,u=b;
				while(vis[v]==0){
					vis[v]=rps;
					v=nx[v];
				}	
				while(vis[u]==0){
					vis[u]=rps;
					u=nx[u];
				}
				if(vis[u]==rps)zr=true;
				if(rpo[v]==rps-1)rpo[v]=rps,ok1=true;
				check(v);
				v1=v;
				if(v!=u){
					v2=u;
					if(rpo[u]==rps-1)rpo[u]=rps,ok2=true;
					check(u);
				}
				if(v1!=-1){
					for(int i=0;i<n;i++){
						for(int j=0;j<g[i].size();j++){
							if(i!=v1&&g[i][j]!=v1)unit(1,i,g[i][j]);
						}
					}
				}
				if(v2!=-1){
					for(int i=0;i<n;i++){
						for(int j=0;j<g[i].size();j++){
							if(i!=v2&&g[i][j]!=v2)unit(2,i,g[i][j]);
						}
					}
				}
			}
		}
	}
	g[a].PB(b);
	g[b].PB(a);
	up(a);
	up(b);
}
int CountCritical() {
	if(zr)return 0;
	return ans;
}

Compilation message (stderr)

rings.cpp: In function 'int unit(int, int, int)':
rings.cpp:16:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
rings.cpp: In function 'void up(int)':
rings.cpp:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[v].size();i++)tr[g[v][i]]++;
               ~^~~~~~~~~~~~
rings.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<g[v].size();i++){
                ~^~~~~~~~~~~~
rings.cpp: In function 'void dfs1(int, int)':
rings.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++){
              ~^~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:122:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j=0;j<g[i].size();j++){
                   ~^~~~~~~~~~~~
rings.cpp:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j=0;j<g[i].size();j++){
                   ~^~~~~~~~~~~~

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