oj.uz

Submission #287705

# Submission time Handle Problem Language Result Execution time Memory
287705 2020-08-31T22:39:45 Z amiratou Parachute rings (IOI12_rings) C++14
100 / 100
 1955 ms 147024 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(!flag4 && (deg[0][A]==3 || deg[0][B]==3) && (deg[0][A]<=3) && (deg[0][B]<=3) && !flag3){ 
		flag3=1;
		assert(deg[0][A]!=deg[0][B]);
		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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 19 ms 24448 KB Output is correct
3 Correct 19 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 18 ms 24336 KB Output is correct
8 Correct 18 ms 24320 KB Output is correct
9 Correct 20 ms 24576 KB Output is correct
10 Correct 19 ms 24576 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 70784 KB Output is correct
2 Correct 1232 ms 111536 KB Output is correct
3 Correct 377 ms 95224 KB Output is correct
4 Correct 1304 ms 114132 KB Output is correct
5 Correct 1302 ms 115600 KB Output is correct
6 Correct 1404 ms 147024 KB Output is correct
7 Correct 366 ms 95860 KB Output is correct
8 Correct 1851 ms 122972 KB Output is correct
9 Correct 1955 ms 129488 KB Output is correct
10 Correct 856 ms 124372 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 19 ms 24448 KB Output is correct
3 Correct 19 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 18 ms 24336 KB Output is correct
8 Correct 18 ms 24320 KB Output is correct
9 Correct 20 ms 24576 KB Output is correct
10 Correct 19 ms 24576 KB Output is correct
11 Correct 19 ms 24576 KB Output is correct
12 Correct 24 ms 25208 KB Output is correct
13 Correct 22 ms 25216 KB Output is correct
14 Correct 20 ms 24960 KB Output is correct
15 Correct 20 ms 25472 KB Output is correct
16 Correct 22 ms 24952 KB Output is correct
17 Correct 23 ms 25216 KB Output is correct
18 Correct 21 ms 25600 KB Output is correct
19 Correct 22 ms 25088 KB Output is correct
20 Correct 23 ms 25208 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 19 ms 24448 KB Output is correct
3 Correct 19 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 18 ms 24336 KB Output is correct
8 Correct 18 ms 24320 KB Output is correct
9 Correct 20 ms 24576 KB Output is correct
10 Correct 19 ms 24576 KB Output is correct
11 Correct 19 ms 24576 KB Output is correct
12 Correct 24 ms 25208 KB Output is correct
13 Correct 22 ms 25216 KB Output is correct
14 Correct 20 ms 24960 KB Output is correct
15 Correct 20 ms 25472 KB Output is correct
16 Correct 22 ms 24952 KB Output is correct
17 Correct 23 ms 25216 KB Output is correct
18 Correct 21 ms 25600 KB Output is correct
19 Correct 22 ms 25088 KB Output is correct
20 Correct 23 ms 25208 KB Output is correct
21 Correct 51 ms 28148 KB Output is correct
22 Correct 54 ms 30576 KB Output is correct
23 Correct 70 ms 32240 KB Output is correct
24 Correct 70 ms 31984 KB Output is correct
25 Correct 34 ms 30328 KB Output is correct
26 Correct 69 ms 34160 KB Output is correct
27 Correct 73 ms 32500 KB Output is correct
28 Correct 112 ms 34424 KB Output is correct
29 Correct 51 ms 32248 KB Output is correct
30 Correct 100 ms 34796 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 19 ms 24448 KB Output is correct
3 Correct 19 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 18 ms 24336 KB Output is correct
8 Correct 18 ms 24320 KB Output is correct
9 Correct 20 ms 24576 KB Output is correct
10 Correct 19 ms 24576 KB Output is correct
11 Correct 565 ms 70784 KB Output is correct
12 Correct 1232 ms 111536 KB Output is correct
13 Correct 377 ms 95224 KB Output is correct
14 Correct 1304 ms 114132 KB Output is correct
15 Correct 1302 ms 115600 KB Output is correct
16 Correct 1404 ms 147024 KB Output is correct
17 Correct 366 ms 95860 KB Output is correct
18 Correct 1851 ms 122972 KB Output is correct
19 Correct 1955 ms 129488 KB Output is correct
20 Correct 856 ms 124372 KB Output is correct
21 Correct 19 ms 24576 KB Output is correct
22 Correct 24 ms 25208 KB Output is correct
23 Correct 22 ms 25216 KB Output is correct
24 Correct 20 ms 24960 KB Output is correct
25 Correct 20 ms 25472 KB Output is correct
26 Correct 22 ms 24952 KB Output is correct
27 Correct 23 ms 25216 KB Output is correct
28 Correct 21 ms 25600 KB Output is correct
29 Correct 22 ms 25088 KB Output is correct
30 Correct 23 ms 25208 KB Output is correct
31 Correct 51 ms 28148 KB Output is correct
32 Correct 54 ms 30576 KB Output is correct
33 Correct 70 ms 32240 KB Output is correct
34 Correct 70 ms 31984 KB Output is correct
35 Correct 34 ms 30328 KB Output is correct
36 Correct 69 ms 34160 KB Output is correct
37 Correct 73 ms 32500 KB Output is correct
38 Correct 112 ms 34424 KB Output is correct
39 Correct 51 ms 32248 KB Output is correct
40 Correct 100 ms 34796 KB Output is correct
41 Correct 272 ms 63076 KB Output is correct
42 Correct 832 ms 106076 KB Output is correct
43 Correct 319 ms 83820 KB Output is correct
44 Correct 354 ms 101500 KB Output is correct
45 Correct 562 ms 109160 KB Output is correct
46 Correct 831 ms 109360 KB Output is correct
47 Correct 1200 ms 133080 KB Output is correct
48 Correct 326 ms 103288 KB Output is correct
49 Correct 810 ms 116432 KB Output is correct
50 Correct 891 ms 115180 KB Output is correct
51 Correct 349 ms 88044 KB Output is correct
52 Correct 1020 ms 111956 KB Output is correct
53 Correct 313 ms 103412 KB Output is correct
54 Correct 1662 ms 120656 KB Output is correct
55 Correct 1214 ms 132620 KB Output is correct