oj.uz

Submission #124488

# Submission time Handle Problem Language Result Execution time Memory
124488 2019-07-03T12:08:26 Z nxteru Parachute rings (IOI12_rings) C++14
37 / 100
 1570 ms 97212 KB 
#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;
	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

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

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 26 ms 24156 KB Output is correct
3 Correct 29 ms 24284 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24392 KB Output is correct
7 Correct 23 ms 23928 KB Output is correct
8 Correct 24 ms 24188 KB Output is correct
9 Correct 25 ms 24184 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 506 ms 47108 KB Output is correct
2 Correct 1010 ms 59112 KB Output is correct
3 Correct 311 ms 37368 KB Output is correct
4 Correct 1312 ms 70764 KB Output is correct
5 Correct 1420 ms 76440 KB Output is correct
6 Correct 1570 ms 97212 KB Output is correct
7 Correct 308 ms 38284 KB Output is correct
8 Correct 1236 ms 64872 KB Output is correct
9 Correct 1295 ms 67784 KB Output is correct
10 Correct 947 ms 69384 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 26 ms 24156 KB Output is correct
3 Correct 29 ms 24284 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24392 KB Output is correct
7 Correct 23 ms 23928 KB Output is correct
8 Correct 24 ms 24188 KB Output is correct
9 Correct 25 ms 24184 KB Output is correct
10 Correct 25 ms 24184 KB Output is correct
11 Incorrect 26 ms 24184 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 26 ms 24156 KB Output is correct
3 Correct 29 ms 24284 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24392 KB Output is correct
7 Correct 23 ms 23928 KB Output is correct
8 Correct 24 ms 24188 KB Output is correct
9 Correct 25 ms 24184 KB Output is correct
10 Correct 25 ms 24184 KB Output is correct
11 Incorrect 26 ms 24184 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 26 ms 24156 KB Output is correct
3 Correct 29 ms 24284 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24392 KB Output is correct
7 Correct 23 ms 23928 KB Output is correct
8 Correct 24 ms 24188 KB Output is correct
9 Correct 25 ms 24184 KB Output is correct
10 Correct 25 ms 24184 KB Output is correct
11 Correct 506 ms 47108 KB Output is correct
12 Correct 1010 ms 59112 KB Output is correct
13 Correct 311 ms 37368 KB Output is correct
14 Correct 1312 ms 70764 KB Output is correct
15 Correct 1420 ms 76440 KB Output is correct
16 Correct 1570 ms 97212 KB Output is correct
17 Correct 308 ms 38284 KB Output is correct
18 Correct 1236 ms 64872 KB Output is correct
19 Correct 1295 ms 67784 KB Output is correct
20 Correct 947 ms 69384 KB Output is correct
21 Incorrect 26 ms 24184 KB Output isn't correct
22 Halted 0 ms 0 KB -