oj.uz

Submission #124483

# Submission time Handle Problem Language Result Execution time Memory
124483 2019-07-03T12:03:13 Z nxteru Parachute rings (IOI12_rings) C++14
37 / 100
 1428 ms 109612 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,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

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 25 ms 23804 KB Output is correct
2 Correct 31 ms 24232 KB Output is correct
3 Correct 30 ms 24188 KB Output is correct
4 Correct 28 ms 23900 KB Output is correct
5 Correct 24 ms 24156 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 23 ms 23932 KB Output is correct
8 Correct 25 ms 24124 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 26 ms 24156 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 55328 KB Output is correct
2 Correct 1099 ms 72272 KB Output is correct
3 Correct 314 ms 52856 KB Output is correct
4 Correct 1271 ms 85912 KB Output is correct
5 Correct 1293 ms 89240 KB Output is correct
6 Correct 1428 ms 109612 KB Output is correct
7 Correct 326 ms 53468 KB Output is correct
8 Correct 1185 ms 80540 KB Output is correct
9 Correct 1409 ms 84232 KB Output is correct
10 Correct 908 ms 83480 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23804 KB Output is correct
2 Correct 31 ms 24232 KB Output is correct
3 Correct 30 ms 24188 KB Output is correct
4 Correct 28 ms 23900 KB Output is correct
5 Correct 24 ms 24156 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 23 ms 23932 KB Output is correct
8 Correct 25 ms 24124 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 26 ms 24156 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 25 ms 23804 KB Output is correct
2 Correct 31 ms 24232 KB Output is correct
3 Correct 30 ms 24188 KB Output is correct
4 Correct 28 ms 23900 KB Output is correct
5 Correct 24 ms 24156 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 23 ms 23932 KB Output is correct
8 Correct 25 ms 24124 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 26 ms 24156 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 25 ms 23804 KB Output is correct
2 Correct 31 ms 24232 KB Output is correct
3 Correct 30 ms 24188 KB Output is correct
4 Correct 28 ms 23900 KB Output is correct
5 Correct 24 ms 24156 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 23 ms 23932 KB Output is correct
8 Correct 25 ms 24124 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 26 ms 24156 KB Output is correct
11 Correct 535 ms 55328 KB Output is correct
12 Correct 1099 ms 72272 KB Output is correct
13 Correct 314 ms 52856 KB Output is correct
14 Correct 1271 ms 85912 KB Output is correct
15 Correct 1293 ms 89240 KB Output is correct
16 Correct 1428 ms 109612 KB Output is correct
17 Correct 326 ms 53468 KB Output is correct
18 Correct 1185 ms 80540 KB Output is correct
19 Correct 1409 ms 84232 KB Output is correct
20 Correct 908 ms 83480 KB Output is correct
21 Incorrect 26 ms 24184 KB Output isn't correct
22 Halted 0 ms 0 KB -