oj.uz

Submission #124497

# Submission time Handle Problem Language Result Execution time Memory
124497 2019-07-03T12:41:18 Z nxteru Parachute rings (IOI12_rings) C++14
37 / 100
 1490 ms 101664 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;
					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;
				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 23800 KB Output is correct
2 Correct 27 ms 24056 KB Output is correct
3 Correct 27 ms 24152 KB Output is correct
4 Correct 24 ms 23956 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 26 ms 24064 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 30 ms 24312 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 51472 KB Output is correct
2 Correct 1067 ms 63500 KB Output is correct
3 Correct 311 ms 41592 KB Output is correct
4 Correct 1377 ms 75040 KB Output is correct
5 Correct 1365 ms 80848 KB Output is correct
6 Correct 1490 ms 101664 KB Output is correct
7 Correct 309 ms 42616 KB Output is correct
8 Correct 1230 ms 69392 KB Output is correct
9 Correct 1340 ms 72100 KB Output is correct
10 Correct 905 ms 73848 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 27 ms 24056 KB Output is correct
3 Correct 27 ms 24152 KB Output is correct
4 Correct 24 ms 23956 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 26 ms 24064 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 30 ms 24312 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 23800 KB Output is correct
2 Correct 27 ms 24056 KB Output is correct
3 Correct 27 ms 24152 KB Output is correct
4 Correct 24 ms 23956 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 26 ms 24064 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 30 ms 24312 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 23800 KB Output is correct
2 Correct 27 ms 24056 KB Output is correct
3 Correct 27 ms 24152 KB Output is correct
4 Correct 24 ms 23956 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 26 ms 24064 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 30 ms 24312 KB Output is correct
11 Correct 550 ms 51472 KB Output is correct
12 Correct 1067 ms 63500 KB Output is correct
13 Correct 311 ms 41592 KB Output is correct
14 Correct 1377 ms 75040 KB Output is correct
15 Correct 1365 ms 80848 KB Output is correct
16 Correct 1490 ms 101664 KB Output is correct
17 Correct 309 ms 42616 KB Output is correct
18 Correct 1230 ms 69392 KB Output is correct
19 Correct 1340 ms 72100 KB Output is correct
20 Correct 905 ms 73848 KB Output is correct
21 Incorrect 26 ms 24184 KB Output isn't correct
22 Halted 0 ms 0 KB -