oj.uz

Submission #287694

# Submission time Handle Problem Language Result Execution time Memory
287694 2020-08-31T22:24:26 Z amiratou Parachute rings (IOI12_rings) C++14
0 / 100
 1848 ms 159832 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)(x.size())
#define fi first
#define se second
const int MX = (int)(1e6+3);
typedef pair<int,int> ii;

int N,deg[6][MX],p[6][MX],s[6][MX],pot[4],k,len;
vector<int> vec[MX],G;
vector<ii> edges;
multiset<int,greater<int> > myset;
bool flag2,flag3,flag4,st,cycle,ok[5];
bitset<MX> vis;

void Init(int N_) {
	N = N_;
	for (int j = 0; j < 6; ++j)
		for (int i = 0; i < N; ++i)
			p[j][i]=i,s[j][i]=1;
}
int findSet(int idx,int i){
	if(p[idx][i]==i)return i;
	return p[idx][i]=findSet(idx,p[idx][i]);
}
bool Union(int idx,int a,int b){
	a=findSet(idx,a),b=findSet(idx,b);
	if(a==b)return 0;
	if(s[idx][a]>s[idx][b])swap(a,b);
	p[idx][a]=b,s[idx][b]+=s[idx][a];
	return 1;
}
void dfs(int node,int par){
	vis[node]=1;G.pb(node);
	for(auto it:vec[node]){
		if(len)return;
		if(it!=par){
			if(vis[it]){
				len=sz(G);
				/*for(auto it:G)
					cerr<<it<<" - ";
				cerr<<"\n";*/
				return;
			}
			dfs(it,node);
		}
	}
	G.pop_back();
}

void Link(int A, int B) {
	if(st)return;
	edges.pb({A,B});
	vec[A].pb(B),vec[B].pb(A);
	deg[0][A]++,deg[0][B]++;
	if(flag3)assert(!flag4);
	if(flag4)assert(!flag3);
	if(!flag3 && !flag4){
		bool h=Union(0,A,B);
		if(!h && cycle){st=1;return;}
		else if(!h){cycle=1;dfs(A,A);}
	}
	if(flag3){
		for (int i = 0; i < 4; ++i){
			if(A==pot[i] || B==pot[i])continue;
			if(!Union(i+1,A,B))ok[i]=0;
			deg[i+1][A]++,deg[i+1][B]++;
			if(deg[i+1][A]>=3 || deg[i+1][B]>=3)ok[i]=0;
		}
	}
	if(k!=A && k!=B && flag4){
		if(!Union(5,A,B)){
			st=1;return;
		}
		deg[5][A]++,deg[5][B]++;
		if(deg[5][A]>=3 || deg[5][B]>=3){st=1;return;}
	}
	if(deg[0][A]==3 || deg[0][B]==3){
		if(flag3){
			bool a=0,b=0;
			if(deg[0][A]!=3)a=1;
			if(deg[0][B]!=3)b=1;
			for (int i = 0; i < 4; ++i)
			{
				if(pot[i]==A)a=1;
				if(pot[i]==B)b=1;
			}
			if(!a || !b)st=1;
		}
		else{ 
			flag3=1;
			if(deg[0][A]!=3)swap(A,B);
			vec[A].pb(A);
			for (int i = 0; i < 4; ++i){
				bool f=1;
				pot[i]=vec[A][i];
				for(auto it:edges){
					if(it.fi!=vec[A][i] && it.se!=vec[A][i]){
						if(!Union(i+1,it.fi,it.se)){f=0;break;}
						deg[i+1][it.fi]++,deg[i+1][it.se]++;
						if(deg[i+1][it.fi]>=3 || deg[i+1][it.se]>=3){f=0;break;}
					}
				}
				ok[i]=f;
			}
			vec[A].pop_back();
		}
	}
	else if(deg[0][A]>=4 || deg[0][B]>=4){
		if(deg[0][A]>=4 && deg[0][B]>=4)st=1;
		else{
			if(deg[0][A]<4)swap(A,B);
			if(A==k)return;
			flag4=1,flag3=0;
			k=A;
			bool f=1;
			for(auto it:edges)
				if(it.fi!=A && it.se!=A){
					if(!Union(5,it.fi,it.se)){f=0;break;}
					deg[5][it.fi]++,deg[5][it.se]++;
					if(deg[5][it.fi]>=3 || deg[5][it.se]>=3){f=0;break;}
				}
			if(!f)st=1;
		}
	}
}

int CountCritical() {
	if(st)return 0;
	if(!flag3 && !flag4){
		if(!cycle)return N;
		else return len;
	}
	if(flag3)
		return ok[0]+ok[1]+ok[2]+ok[3];
	if(flag4)return 1;
	return -1;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 19 ms 24480 KB Output is correct
3 Correct 21 ms 24576 KB Output is correct
4 Correct 17 ms 24064 KB Output is correct
5 Correct 18 ms 24320 KB Output is correct
6 Correct 19 ms 24704 KB Output is correct
7 Correct 17 ms 24320 KB Output is correct
8 Correct 19 ms 24320 KB Output is correct
9 Correct 19 ms 24576 KB Output is correct
10 Incorrect 19 ms 24576 KB Output isn't correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 71516 KB Output is correct
2 Correct 1191 ms 112044 KB Output is correct
3 Correct 339 ms 103544 KB Output is correct
4 Correct 1278 ms 127452 KB Output is correct
5 Correct 1302 ms 128976 KB Output is correct
6 Correct 1454 ms 159832 KB Output is correct
7 Correct 332 ms 103288 KB Output is correct
8 Correct 1848 ms 135376 KB Output is correct
9 Incorrect 1751 ms 142092 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 19 ms 24480 KB Output is correct
3 Correct 21 ms 24576 KB Output is correct
4 Correct 17 ms 24064 KB Output is correct
5 Correct 18 ms 24320 KB Output is correct
6 Correct 19 ms 24704 KB Output is correct
7 Correct 17 ms 24320 KB Output is correct
8 Correct 19 ms 24320 KB Output is correct
9 Correct 19 ms 24576 KB Output is correct
10 Incorrect 19 ms 24576 KB Output isn't correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 19 ms 24480 KB Output is correct
3 Correct 21 ms 24576 KB Output is correct
4 Correct 17 ms 24064 KB Output is correct
5 Correct 18 ms 24320 KB Output is correct
6 Correct 19 ms 24704 KB Output is correct
7 Correct 17 ms 24320 KB Output is correct
8 Correct 19 ms 24320 KB Output is correct
9 Correct 19 ms 24576 KB Output is correct
10 Incorrect 19 ms 24576 KB Output isn't correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 19 ms 24480 KB Output is correct
3 Correct 21 ms 24576 KB Output is correct
4 Correct 17 ms 24064 KB Output is correct
5 Correct 18 ms 24320 KB Output is correct
6 Correct 19 ms 24704 KB Output is correct
7 Correct 17 ms 24320 KB Output is correct
8 Correct 19 ms 24320 KB Output is correct
9 Correct 19 ms 24576 KB Output is correct
10 Incorrect 19 ms 24576 KB Output isn't correct