oj.uz

Submission #121175

# Submission time Handle Problem Language Result Execution time Memory
121175 2019-06-26T07:34:28 Z baluteshih Parachute rings (IOI12_rings) C++14
100 / 100
 3434 ms 103864 KB 
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int C=5;
int N,boss[5][1000005],upd,tag[1000005],flag,flag2,ans[C],sz[C][1000005],cir;
vector<int> G[1000005],pos;

void Init(int N_)
{
	N=N_;
	for(int j=0;j<4;++j)
		ans[j]=1;
	for(int i=0;i<N;++i)
		for(int j=0;j<C;++j)
			boss[j][i]=i;
}

int finds(int t,int a)
{
	if(boss[t][a]==a) return a;
	return boss[t][a]=finds(t,boss[t][a]);
}

bool Union(int t,int a,int b)
{
	a=finds(t,a),b=finds(t,b);
	if(a==b) return 0;
	boss[t][a]=b;
	return 1;
}

void update(int x)
{
	++upd,pos.pb(x);
	for(int i:G[x])
		pos.pb(i);
	for(int i=0;i<pos.size();++i)
	{
		for(int j=0;j<N;++j)
			if(j!=pos[i])	
				for(int k:G[j])
					if(k!=pos[i]&&j<k)
						ans[i]&=Union(i,j,k),++sz[i][j],++sz[i][k];
		for(int j=0;j<N;++j)
			if(j!=pos[i])
				ans[i]&=(sz[i][j]<3);
	}
}

void add_edge(int a,int b)
{
	for(int i=0;i<4;++i)
		if(a!=pos[i]&&b!=pos[i])
		{
			ans[i]&=Union(i,a,b);
			++sz[i][a],++sz[i][b];
			ans[i]&=(sz[i][a]<3),ans[i]&=(sz[i][b]<3);
		}
}

void Link(int A, int B)
{
	G[A].pb(B),G[B].pb(A);
	if(flag) add_edge(A,B);
	if(!flag&&G[A].size()==3) flag=1,update(A);
	if(!flag&&G[B].size()==3) flag=1,update(B);
	if(!flag)
		if(!Union(4,A,B))
			if(!flag2)
				for(int i=(flag2=1,0);i<N;++i)
					cir+=(finds(4,i)==finds(4,A));
			else
				cir=0;
}

int CountCritical()
{
	if(flag) return ans[0]+ans[1]+ans[2]+ans[3];
	if(flag2) return cir;
	return N;
}

Compilation message

rings.cpp: In function 'void update(int)':
rings.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pos.size();++i)
              ~^~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:80:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if(!Union(4,A,B))
     ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 24184 KB Output is correct
3 Correct 23 ms 24320 KB Output is correct
4 Correct 21 ms 23872 KB Output is correct
5 Correct 22 ms 24064 KB Output is correct
6 Correct 24 ms 24184 KB Output is correct
7 Correct 21 ms 24064 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 24320 KB Output is correct
10 Correct 24 ms 24312 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 50468 KB Output is correct
2 Correct 2318 ms 77324 KB Output is correct
3 Correct 3434 ms 86332 KB Output is correct
4 Correct 1285 ms 74872 KB Output is correct
5 Correct 1292 ms 75000 KB Output is correct
6 Correct 1243 ms 86700 KB Output is correct
7 Correct 3393 ms 98052 KB Output is correct
8 Correct 2400 ms 98792 KB Output is correct
9 Correct 2390 ms 103864 KB Output is correct
10 Correct 851 ms 86136 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 24184 KB Output is correct
3 Correct 23 ms 24320 KB Output is correct
4 Correct 21 ms 23872 KB Output is correct
5 Correct 22 ms 24064 KB Output is correct
6 Correct 24 ms 24184 KB Output is correct
7 Correct 21 ms 24064 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 24320 KB Output is correct
10 Correct 24 ms 24312 KB Output is correct
11 Correct 24 ms 24320 KB Output is correct
12 Correct 27 ms 24824 KB Output is correct
13 Correct 28 ms 24704 KB Output is correct
14 Correct 26 ms 24440 KB Output is correct
15 Correct 27 ms 24832 KB Output is correct
16 Correct 27 ms 24568 KB Output is correct
17 Correct 27 ms 24632 KB Output is correct
18 Correct 29 ms 25208 KB Output is correct
19 Correct 26 ms 24448 KB Output is correct
20 Correct 27 ms 24704 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 24184 KB Output is correct
3 Correct 23 ms 24320 KB Output is correct
4 Correct 21 ms 23872 KB Output is correct
5 Correct 22 ms 24064 KB Output is correct
6 Correct 24 ms 24184 KB Output is correct
7 Correct 21 ms 24064 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 24320 KB Output is correct
10 Correct 24 ms 24312 KB Output is correct
11 Correct 24 ms 24320 KB Output is correct
12 Correct 27 ms 24824 KB Output is correct
13 Correct 28 ms 24704 KB Output is correct
14 Correct 26 ms 24440 KB Output is correct
15 Correct 27 ms 24832 KB Output is correct
16 Correct 27 ms 24568 KB Output is correct
17 Correct 27 ms 24632 KB Output is correct
18 Correct 29 ms 25208 KB Output is correct
19 Correct 26 ms 24448 KB Output is correct
20 Correct 27 ms 24704 KB Output is correct
21 Correct 45 ms 26248 KB Output is correct
22 Correct 56 ms 27640 KB Output is correct
23 Correct 62 ms 28664 KB Output is correct
24 Correct 83 ms 29560 KB Output is correct
25 Correct 40 ms 27940 KB Output is correct
26 Correct 79 ms 30300 KB Output is correct
27 Correct 73 ms 29304 KB Output is correct
28 Correct 86 ms 30840 KB Output is correct
29 Correct 71 ms 29728 KB Output is correct
30 Correct 87 ms 30072 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 24184 KB Output is correct
3 Correct 23 ms 24320 KB Output is correct
4 Correct 21 ms 23872 KB Output is correct
5 Correct 22 ms 24064 KB Output is correct
6 Correct 24 ms 24184 KB Output is correct
7 Correct 21 ms 24064 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 24320 KB Output is correct
10 Correct 24 ms 24312 KB Output is correct
11 Correct 444 ms 50468 KB Output is correct
12 Correct 2318 ms 77324 KB Output is correct
13 Correct 3434 ms 86332 KB Output is correct
14 Correct 1285 ms 74872 KB Output is correct
15 Correct 1292 ms 75000 KB Output is correct
16 Correct 1243 ms 86700 KB Output is correct
17 Correct 3393 ms 98052 KB Output is correct
18 Correct 2400 ms 98792 KB Output is correct
19 Correct 2390 ms 103864 KB Output is correct
20 Correct 851 ms 86136 KB Output is correct
21 Correct 24 ms 24320 KB Output is correct
22 Correct 27 ms 24824 KB Output is correct
23 Correct 28 ms 24704 KB Output is correct
24 Correct 26 ms 24440 KB Output is correct
25 Correct 27 ms 24832 KB Output is correct
26 Correct 27 ms 24568 KB Output is correct
27 Correct 27 ms 24632 KB Output is correct
28 Correct 29 ms 25208 KB Output is correct
29 Correct 26 ms 24448 KB Output is correct
30 Correct 27 ms 24704 KB Output is correct
31 Correct 45 ms 26248 KB Output is correct
32 Correct 56 ms 27640 KB Output is correct
33 Correct 62 ms 28664 KB Output is correct
34 Correct 83 ms 29560 KB Output is correct
35 Correct 40 ms 27940 KB Output is correct
36 Correct 79 ms 30300 KB Output is correct
37 Correct 73 ms 29304 KB Output is correct
38 Correct 86 ms 30840 KB Output is correct
39 Correct 71 ms 29728 KB Output is correct
40 Correct 87 ms 30072 KB Output is correct
41 Correct 232 ms 45800 KB Output is correct
42 Correct 910 ms 76512 KB Output is correct
43 Correct 411 ms 63544 KB Output is correct
44 Correct 1422 ms 96600 KB Output is correct
45 Correct 2065 ms 89096 KB Output is correct
46 Correct 800 ms 77988 KB Output is correct
47 Correct 1099 ms 79112 KB Output is correct
48 Correct 1166 ms 82296 KB Output is correct
49 Correct 789 ms 79456 KB Output is correct
50 Correct 852 ms 79076 KB Output is correct
51 Correct 553 ms 60772 KB Output is correct
52 Correct 1230 ms 83228 KB Output is correct
53 Correct 1334 ms 82592 KB Output is correct
54 Correct 2329 ms 89292 KB Output is correct
55 Correct 2938 ms 95064 KB Output is correct