Submission #270180

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
270180	2020-08-17T12:59:24 Z	Saboon	Parachute rings (IOI12_rings)	C++14	100 / 100	1623 ms	109812 KB

rings

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int N;
int par[maxn][6], deg[maxn][6];
int e1[maxn], e2[maxn], m = 0;
bool three = false;
int a[6], good[6];
vector<int> g[maxn];
int cntcyc = -1;

int get_par(int v, int c){
	return par[v][c] < 0 ? v : par[v][c] = get_par(par[v][c],c);
}

void merge(int v, int u, int c){
	if (!good[c])
		return;
	int vp = get_par(v,c), up = get_par(u,c);
	if (vp == up){
		good[c] = 0;
		return;
	}
	if (deg[v][c] > 1 or deg[u][c] > 1){
		good[c] = 0;
		return;
	}
	deg[v][c] ++, deg[u][c] ++;
	par[vp][c] = up;
}

void Init(int N_){
	N = N_;
	memset(par, -1, sizeof par);
	for (int i = 1; i <= 4; i++)
		good[i] = 1;
}

void Link(int v, int u){
	if (g[v].size() < g[u].size())
		swap(v,u);
	g[v].push_back(u), g[u].push_back(v);
	if (g[v].size() == 3 and three == false){
		three = true;
		a[1] = v;
		for (int j = 0; j < 3; j++)
			a[j+2] = g[v][j];
		for (int j = 1; j <= 4; j++){
			for (int i = 0; i < m; i++){
				int v = e1[i], u = e2[i];
				if (v != a[j] and u != a[j])
					merge(v,u,j);
			}
		}
	}
	e1[m] = v, e2[m] = u, m++;
	if (three){
		for (int j = 1; j <= 4; j++){
			int v = e1[m-1], u = e2[m-1];
			if (v != a[j] and u != a[j])
				merge(v,u,j);
		}
		return;
	}
	if (get_par(v,0) == get_par(u,0)){
		if (cntcyc == -1)
			cntcyc = -par[get_par(v,0)][0];
		else
			cntcyc = 0;
	}
	else{
		v = get_par(v,0), u = get_par(u,0);
		par[u][0] += par[v][0];
		par[v][0] = u;
	}
}

int CountCritical(){
	if (three == 0){
		if (cntcyc == -1)
			return N;
		return cntcyc;
	}
	int ret = 0;
	for (int i = 1; i <= 4; i++)
		if (good[i])
			ret ++;
	return ret;
}

Subtask #1
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	47352 KB	Output is correct
2	Correct	34 ms	47616 KB	Output is correct
3	Correct	30 ms	47616 KB	Output is correct
4	Correct	28 ms	47360 KB	Output is correct
5	Correct	30 ms	47488 KB	Output is correct
6	Correct	30 ms	47488 KB	Output is correct
7	Correct	41 ms	47480 KB	Output is correct
8	Correct	29 ms	47488 KB	Output is correct
9	Correct	30 ms	47616 KB	Output is correct
10	Correct	30 ms	47720 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	462 ms	67704 KB	Output is correct
2	Correct	1055 ms	97400 KB	Output is correct
3	Correct	822 ms	103672 KB	Output is correct
4	Correct	1114 ms	86396 KB	Output is correct
5	Correct	1134 ms	86520 KB	Output is correct
6	Correct	1245 ms	85252 KB	Output is correct
7	Correct	1012 ms	103660 KB	Output is correct
8	Correct	1584 ms	105796 KB	Output is correct
9	Correct	1623 ms	109812 KB	Output is correct
10	Correct	967 ms	85496 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	47352 KB	Output is correct
2	Correct	34 ms	47616 KB	Output is correct
3	Correct	30 ms	47616 KB	Output is correct
4	Correct	28 ms	47360 KB	Output is correct
5	Correct	30 ms	47488 KB	Output is correct
6	Correct	30 ms	47488 KB	Output is correct
7	Correct	41 ms	47480 KB	Output is correct
8	Correct	29 ms	47488 KB	Output is correct
9	Correct	30 ms	47616 KB	Output is correct
10	Correct	30 ms	47720 KB	Output is correct
11	Correct	36 ms	47608 KB	Output is correct
12	Correct	39 ms	47996 KB	Output is correct
13	Correct	41 ms	48000 KB	Output is correct
14	Correct	32 ms	47864 KB	Output is correct
15	Correct	32 ms	48032 KB	Output is correct
16	Correct	33 ms	47776 KB	Output is correct
17	Correct	33 ms	47992 KB	Output is correct
18	Correct	33 ms	48248 KB	Output is correct
19	Correct	35 ms	47744 KB	Output is correct
20	Correct	33 ms	48000 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	47352 KB	Output is correct
2	Correct	34 ms	47616 KB	Output is correct
3	Correct	30 ms	47616 KB	Output is correct
4	Correct	28 ms	47360 KB	Output is correct
5	Correct	30 ms	47488 KB	Output is correct
6	Correct	30 ms	47488 KB	Output is correct
7	Correct	41 ms	47480 KB	Output is correct
8	Correct	29 ms	47488 KB	Output is correct
9	Correct	30 ms	47616 KB	Output is correct
10	Correct	30 ms	47720 KB	Output is correct
11	Correct	36 ms	47608 KB	Output is correct
12	Correct	39 ms	47996 KB	Output is correct
13	Correct	41 ms	48000 KB	Output is correct
14	Correct	32 ms	47864 KB	Output is correct
15	Correct	32 ms	48032 KB	Output is correct
16	Correct	33 ms	47776 KB	Output is correct
17	Correct	33 ms	47992 KB	Output is correct
18	Correct	33 ms	48248 KB	Output is correct
19	Correct	35 ms	47744 KB	Output is correct
20	Correct	33 ms	48000 KB	Output is correct
21	Correct	55 ms	48636 KB	Output is correct
22	Correct	73 ms	49272 KB	Output is correct
23	Correct	70 ms	49784 KB	Output is correct
24	Correct	77 ms	51576 KB	Output is correct
25	Correct	49 ms	50040 KB	Output is correct
26	Correct	79 ms	52216 KB	Output is correct
27	Correct	81 ms	50808 KB	Output is correct
28	Correct	76 ms	52860 KB	Output is correct
29	Correct	63 ms	51576 KB	Output is correct
30	Correct	115 ms	51324 KB	Output is correct

Subtask #5
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	47352 KB	Output is correct
2	Correct	34 ms	47616 KB	Output is correct
3	Correct	30 ms	47616 KB	Output is correct
4	Correct	28 ms	47360 KB	Output is correct
5	Correct	30 ms	47488 KB	Output is correct
6	Correct	30 ms	47488 KB	Output is correct
7	Correct	41 ms	47480 KB	Output is correct
8	Correct	29 ms	47488 KB	Output is correct
9	Correct	30 ms	47616 KB	Output is correct
10	Correct	30 ms	47720 KB	Output is correct
11	Correct	462 ms	67704 KB	Output is correct
12	Correct	1055 ms	97400 KB	Output is correct
13	Correct	822 ms	103672 KB	Output is correct
14	Correct	1114 ms	86396 KB	Output is correct
15	Correct	1134 ms	86520 KB	Output is correct
16	Correct	1245 ms	85252 KB	Output is correct
17	Correct	1012 ms	103660 KB	Output is correct
18	Correct	1584 ms	105796 KB	Output is correct
19	Correct	1623 ms	109812 KB	Output is correct
20	Correct	967 ms	85496 KB	Output is correct
21	Correct	36 ms	47608 KB	Output is correct
22	Correct	39 ms	47996 KB	Output is correct
23	Correct	41 ms	48000 KB	Output is correct
24	Correct	32 ms	47864 KB	Output is correct
25	Correct	32 ms	48032 KB	Output is correct
26	Correct	33 ms	47776 KB	Output is correct
27	Correct	33 ms	47992 KB	Output is correct
28	Correct	33 ms	48248 KB	Output is correct
29	Correct	35 ms	47744 KB	Output is correct
30	Correct	33 ms	48000 KB	Output is correct
31	Correct	55 ms	48636 KB	Output is correct
32	Correct	73 ms	49272 KB	Output is correct
33	Correct	70 ms	49784 KB	Output is correct
34	Correct	77 ms	51576 KB	Output is correct
35	Correct	49 ms	50040 KB	Output is correct
36	Correct	79 ms	52216 KB	Output is correct
37	Correct	81 ms	50808 KB	Output is correct
38	Correct	76 ms	52860 KB	Output is correct
39	Correct	63 ms	51576 KB	Output is correct
40	Correct	115 ms	51324 KB	Output is correct
41	Correct	297 ms	57592 KB	Output is correct
42	Correct	619 ms	86520 KB	Output is correct
43	Correct	301 ms	73336 KB	Output is correct
44	Correct	731 ms	94584 KB	Output is correct
45	Correct	712 ms	96632 KB	Output is correct
46	Correct	859 ms	80668 KB	Output is correct
47	Correct	1018 ms	81120 KB	Output is correct
48	Correct	515 ms	89288 KB	Output is correct
49	Correct	787 ms	78544 KB	Output is correct
50	Correct	800 ms	78280 KB	Output is correct
51	Correct	326 ms	72372 KB	Output is correct
52	Correct	585 ms	87804 KB	Output is correct
53	Correct	502 ms	88480 KB	Output is correct
54	Correct	1396 ms	98368 KB	Output is correct
55	Correct	1162 ms	102896 KB	Output is correct

Submission #270180

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 31.0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
31.0 / 31.0