Submission #124483

#	Time	Username	Problem	Language	Result	Execution time	Memory
124483		nxteru	Parachute rings (IOI12_rings)	C++14	37 / 100	1428 ms	109612 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
int n,par[1000005],ins,rps,ino[1000005],rpo[1000005],in[1000005],ts,ans,nx[1000005],vis[1000005],fr=-1,tr[1000005],trs;
bool zr,rpt;
vector<int>g[1000005];
int find(int x){
	if(par[x]==x)return x;
	return par[x]=find(par[x]);
}
bool same(int x,int y){
	return find(x)==find(y);
}
int unit(int x,int y){
	par[find(y)]=find(x);
}
void Init(int N){
	n=N;
	for(int i=0;i<n;i++)par[i]=i,nx[i]=-1,vis[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(!same(a,b)){
		unit(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{
			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;
					a=nx[v];
				}	
				while(vis[u]==0){
					vis[u]=rps;
					b=nx[u];
				}
				if(vis[u]==rps)zr=true;
				if(rpo[v]==rps-1)rpo[v]=rps;
				check(v);
				if(v!=u){
					if(rpo[v]==rps-1)rpo[v]=rps;
					check(u);
				}
			}
		}
	}
	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)':
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++){
              ~^~~~~~~~~~~~

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