oj.uz

Submission #124809

# Submission time Handle Problem Language Result Execution time Memory
124809 2019-07-04T02:24:28 Z nxteru Parachute rings (IOI12_rings) C++14
37 / 100
 1459 ms 117368 KB 
#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;
		unit(1,a,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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 24 ms 24184 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 24 ms 24184 KB Output is correct
6 Correct 25 ms 24440 KB Output is correct
7 Correct 22 ms 24056 KB Output is correct
8 Correct 24 ms 24184 KB Output is correct
9 Correct 25 ms 24312 KB Output is correct
10 Correct 25 ms 24184 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 57208 KB Output is correct
2 Correct 1047 ms 75512 KB Output is correct
3 Correct 317 ms 56952 KB Output is correct
4 Correct 1286 ms 91288 KB Output is correct
5 Correct 1287 ms 96920 KB Output is correct
6 Correct 1459 ms 117368 KB Output is correct
7 Correct 313 ms 57332 KB Output is correct
8 Correct 1178 ms 84112 KB Output is correct
9 Correct 1274 ms 88200 KB Output is correct
10 Correct 911 ms 89180 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 24 ms 24184 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 24 ms 24184 KB Output is correct
6 Correct 25 ms 24440 KB Output is correct
7 Correct 22 ms 24056 KB Output is correct
8 Correct 24 ms 24184 KB Output is correct
9 Correct 25 ms 24312 KB Output is correct
10 Correct 25 ms 24184 KB Output is correct
11 Correct 25 ms 24312 KB Output is correct
12 Correct 28 ms 24568 KB Output is correct
13 Correct 27 ms 24568 KB Output is correct
14 Incorrect 27 ms 24404 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 24 ms 24184 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 24 ms 24184 KB Output is correct
6 Correct 25 ms 24440 KB Output is correct
7 Correct 22 ms 24056 KB Output is correct
8 Correct 24 ms 24184 KB Output is correct
9 Correct 25 ms 24312 KB Output is correct
10 Correct 25 ms 24184 KB Output is correct
11 Correct 25 ms 24312 KB Output is correct
12 Correct 28 ms 24568 KB Output is correct
13 Correct 27 ms 24568 KB Output is correct
14 Incorrect 27 ms 24404 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 24 ms 24184 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 24 ms 24184 KB Output is correct
6 Correct 25 ms 24440 KB Output is correct
7 Correct 22 ms 24056 KB Output is correct
8 Correct 24 ms 24184 KB Output is correct
9 Correct 25 ms 24312 KB Output is correct
10 Correct 25 ms 24184 KB Output is correct
11 Correct 507 ms 57208 KB Output is correct
12 Correct 1047 ms 75512 KB Output is correct
13 Correct 317 ms 56952 KB Output is correct
14 Correct 1286 ms 91288 KB Output is correct
15 Correct 1287 ms 96920 KB Output is correct
16 Correct 1459 ms 117368 KB Output is correct
17 Correct 313 ms 57332 KB Output is correct
18 Correct 1178 ms 84112 KB Output is correct
19 Correct 1274 ms 88200 KB Output is correct
20 Correct 911 ms 89180 KB Output is correct
21 Correct 25 ms 24312 KB Output is correct
22 Correct 28 ms 24568 KB Output is correct
23 Correct 27 ms 24568 KB Output is correct
24 Incorrect 27 ms 24404 KB Output isn't correct
25 Halted 0 ms 0 KB -