oj.uz

Submission #107560

# Submission time Handle Problem Language Result Execution time Memory
107560 2019-04-25T07:52:27 Z ekrem Parachute rings (IOI12_rings) C++
100 / 100
 2126 ms 117372 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, m, k, f, ata[5][N], kom[5][N],dur[5], ne[5], son[5], say, vis[N];
ii b[N];
vector < int > g[N];

int atabul(int d, int x){return ata[d][x] = (ata[d][x] != x) ? atabul(d, ata[d][x]) : x;}

bool bir(int d, int u, int v){
	int xx = atabul(d, u);
	int yy = atabul(d, v);
	if(xx != yy){
		if(rand()%2)
			ata[d][xx] = yy;
		else
			ata[d][yy] = xx;
		return 1;
	}
	return 0;
}

void Init(int nn){

	srand(time(0));

	n = nn;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < 5; j++)
			ata[j][i] = i;

	for(int i = 1; i <= 4; i++){
		son[i] = dur[i] = 1;
	}

	dur[0] = n;
}

void dfs(int node){
	say++;
	vis[node] = 1;
	for(int i = 0; i < g[node].size(); i++)
		if(!vis[g[node][i]])
			dfs(g[node][i]);
}

void Link(int u, int v){
	u++;v++;
	kom[0][u]++;
	kom[0][v]++;

	g[u].pb(v);
	g[v].pb(u);

	b[++m] = mp(u, v);
	
	if(!f){
		if(kom[0][u] == 3){
			dur[0] = 0;
			f = 1;
			ne[++k] = u;
			for(int i = 0; i < g[u].size(); i++)
				ne[++k] = g[u][i];
		} else if(kom[0][v] == 3){
			dur[0] = 0;
			f = 1;
			ne[++k] = v;
			for(int i = 0; i < g[v].size(); i++)
				ne[++k] = g[v][i];
			// cout << "Pat" << " " << ne[1] << " " << ne[2] << " " << ne[3] << " " << ne[4] << endl;
		} else{
			if(!bir(0, u, v)){
				if(dur[0] != n)
					dur[0] = 0;
				else{
					say = 0;
					dfs(u);
					dur[0] = say;
				}
			}
		}
	}
}

int CountCritical(){
	if(!f)
		return dur[0];
	int ans = 0;
	for(int i = 1; i <= 4; i++){
		if(!dur[i])
			continue;
		for(;son[i] <= m; son[i]++){
			int u = b[son[i]].st;
			int v = b[son[i]].nd;
			if(u == ne[i] or v == ne[i])
				continue;
			// cout << i << " " << u << " " << v << endl;
			kom[i][u]++;
			kom[i][v]++;
			if(kom[i][u] == 3)
				dur[i] = 0;
			if(kom[i][v] == 3)
				dur[i] = 0;
			if(!bir(i, u, v))
				dur[i] = 0;
		}
		ans += dur[i];
	}
	return ans;
}

// int main() {
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// 	Init(7);
// 	cout << CountCritical() << endl;
// 	Link(1, 2);
// 	cout << CountCritical() << endl;	
// 	Link(0, 5);
// 	cout << CountCritical() << endl;	
// 	Link(2, 0);
// 	cout << CountCritical() << endl;	
// 	Link(3, 2);
// 	cout << CountCritical() << endl;	
// 	Link(3, 5);
// 	cout << CountCritical() << endl;	
// 	Link(4, 3);
// 	cout << CountCritical() << endl;	
// 	return 0;
// }

Compilation message

rings.cpp: In function 'void dfs(int)':
rings.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:71:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < g[u].size(); i++)
                   ~~^~~~~~~~~~~~~
rings.cpp:77:21: 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 29 ms 23808 KB Output is correct
2 Correct 30 ms 24376 KB Output is correct
3 Correct 30 ms 24312 KB Output is correct
4 Correct 30 ms 24004 KB Output is correct
5 Correct 28 ms 24192 KB Output is correct
6 Correct 29 ms 24448 KB Output is correct
7 Correct 26 ms 24120 KB Output is correct
8 Correct 28 ms 24184 KB Output is correct
9 Correct 31 ms 24320 KB Output is correct
10 Correct 34 ms 24312 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 63532 KB Output is correct
2 Correct 1297 ms 97300 KB Output is correct
3 Correct 2029 ms 110416 KB Output is correct
4 Correct 1437 ms 101496 KB Output is correct
5 Correct 1499 ms 104568 KB Output is correct
6 Correct 1758 ms 117372 KB Output is correct
7 Correct 2122 ms 108972 KB Output is correct
8 Correct 1886 ms 109712 KB Output is correct
9 Correct 2126 ms 115508 KB Output is correct
10 Correct 1025 ms 100104 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23808 KB Output is correct
2 Correct 30 ms 24376 KB Output is correct
3 Correct 30 ms 24312 KB Output is correct
4 Correct 30 ms 24004 KB Output is correct
5 Correct 28 ms 24192 KB Output is correct
6 Correct 29 ms 24448 KB Output is correct
7 Correct 26 ms 24120 KB Output is correct
8 Correct 28 ms 24184 KB Output is correct
9 Correct 31 ms 24320 KB Output is correct
10 Correct 34 ms 24312 KB Output is correct
11 Correct 31 ms 24320 KB Output is correct
12 Correct 31 ms 24828 KB Output is correct
13 Correct 29 ms 24832 KB Output is correct
14 Correct 27 ms 24668 KB Output is correct
15 Correct 31 ms 24832 KB Output is correct
16 Correct 33 ms 24704 KB Output is correct
17 Correct 29 ms 24832 KB Output is correct
18 Correct 33 ms 25336 KB Output is correct
19 Correct 30 ms 24704 KB Output is correct
20 Correct 31 ms 24824 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23808 KB Output is correct
2 Correct 30 ms 24376 KB Output is correct
3 Correct 30 ms 24312 KB Output is correct
4 Correct 30 ms 24004 KB Output is correct
5 Correct 28 ms 24192 KB Output is correct
6 Correct 29 ms 24448 KB Output is correct
7 Correct 26 ms 24120 KB Output is correct
8 Correct 28 ms 24184 KB Output is correct
9 Correct 31 ms 24320 KB Output is correct
10 Correct 34 ms 24312 KB Output is correct
11 Correct 31 ms 24320 KB Output is correct
12 Correct 31 ms 24828 KB Output is correct
13 Correct 29 ms 24832 KB Output is correct
14 Correct 27 ms 24668 KB Output is correct
15 Correct 31 ms 24832 KB Output is correct
16 Correct 33 ms 24704 KB Output is correct
17 Correct 29 ms 24832 KB Output is correct
18 Correct 33 ms 25336 KB Output is correct
19 Correct 30 ms 24704 KB Output is correct
20 Correct 31 ms 24824 KB Output is correct
21 Correct 56 ms 26744 KB Output is correct
22 Correct 75 ms 28332 KB Output is correct
23 Correct 73 ms 29432 KB Output is correct
24 Correct 89 ms 29328 KB Output is correct
25 Correct 44 ms 27520 KB Output is correct
26 Correct 79 ms 31096 KB Output is correct
27 Correct 114 ms 30480 KB Output is correct
28 Correct 81 ms 32040 KB Output is correct
29 Correct 64 ms 30344 KB Output is correct
30 Correct 108 ms 31992 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23808 KB Output is correct
2 Correct 30 ms 24376 KB Output is correct
3 Correct 30 ms 24312 KB Output is correct
4 Correct 30 ms 24004 KB Output is correct
5 Correct 28 ms 24192 KB Output is correct
6 Correct 29 ms 24448 KB Output is correct
7 Correct 26 ms 24120 KB Output is correct
8 Correct 28 ms 24184 KB Output is correct
9 Correct 31 ms 24320 KB Output is correct
10 Correct 34 ms 24312 KB Output is correct
11 Correct 656 ms 63532 KB Output is correct
12 Correct 1297 ms 97300 KB Output is correct
13 Correct 2029 ms 110416 KB Output is correct
14 Correct 1437 ms 101496 KB Output is correct
15 Correct 1499 ms 104568 KB Output is correct
16 Correct 1758 ms 117372 KB Output is correct
17 Correct 2122 ms 108972 KB Output is correct
18 Correct 1886 ms 109712 KB Output is correct
19 Correct 2126 ms 115508 KB Output is correct
20 Correct 1025 ms 100104 KB Output is correct
21 Correct 31 ms 24320 KB Output is correct
22 Correct 31 ms 24828 KB Output is correct
23 Correct 29 ms 24832 KB Output is correct
24 Correct 27 ms 24668 KB Output is correct
25 Correct 31 ms 24832 KB Output is correct
26 Correct 33 ms 24704 KB Output is correct
27 Correct 29 ms 24832 KB Output is correct
28 Correct 33 ms 25336 KB Output is correct
29 Correct 30 ms 24704 KB Output is correct
30 Correct 31 ms 24824 KB Output is correct
31 Correct 56 ms 26744 KB Output is correct
32 Correct 75 ms 28332 KB Output is correct
33 Correct 73 ms 29432 KB Output is correct
34 Correct 89 ms 29328 KB Output is correct
35 Correct 44 ms 27520 KB Output is correct
36 Correct 79 ms 31096 KB Output is correct
37 Correct 114 ms 30480 KB Output is correct
38 Correct 81 ms 32040 KB Output is correct
39 Correct 64 ms 30344 KB Output is correct
40 Correct 108 ms 31992 KB Output is correct
41 Correct 291 ms 49528 KB Output is correct
42 Correct 905 ms 83028 KB Output is correct
43 Correct 315 ms 57976 KB Output is correct
44 Correct 863 ms 107256 KB Output is correct
45 Correct 964 ms 97656 KB Output is correct
46 Correct 983 ms 88184 KB Output is correct
47 Correct 1350 ms 101096 KB Output is correct
48 Correct 556 ms 88616 KB Output is correct
49 Correct 945 ms 88924 KB Output is correct
50 Correct 1049 ms 88252 KB Output is correct
51 Correct 396 ms 63680 KB Output is correct
52 Correct 730 ms 92672 KB Output is correct
53 Correct 606 ms 88956 KB Output is correct
54 Correct 1634 ms 98756 KB Output is correct
55 Correct 1406 ms 105464 KB Output is correct