Submission #351190

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
351190	2021-01-19T14:57:40 Z	juggernaut	Parachute rings (IOI12_rings)	C++14	100 / 100	1490 ms	99108 KB

rings

//JUST UNDERSTANDED THE MAIN IDEA
#include <bits/stdc++.h>
using namespace std;
#define SZ 1234567
#define pb push_back
vector<int> adj[SZ];
int n,stage,ff[SZ],d[4],sz[SZ];
int gf(int x) {return ff[x]?ff[x]=gf(ff[x]):x;}
vector<int> ps;
void uni(int a,int b)
{
	a=gf(a),b=gf(b);
	if(a==b) ps.pb(a);
	else ff[a]=b,sz[b]+=sz[a];
}
void Init(int N_)
{
	n=N_; stage=0;
	for(int i=1;i<=n;++i) sz[i]=1;
}
struct DS
{
int u,good=1;
int ff[SZ],deg[SZ];
int gf(int x) {return ff[x]?ff[x]=gf(ff[x]):x;}
void init(int t)
{
	u=t;
}
void adde(int a,int b)
{
	if(a==u||b==u) return;
	good&=(++deg[a])<=2;
	good&=(++deg[b])<=2;
	a=gf(a),b=gf(b);
	if(a==b) good=0;
	else ff[a]=b;
}
int calc()
{return good;}
}S[4];
void rebuild(int t)
{
	for(int i=0;i<3;++i) S[i].init(adj[t][i]);
	S[3].init(t);
	for(int i=1;i<=n;++i)
		for(auto b:adj[i]) if(i<b)
			for(int k=0;k<4;++k)
				S[k].adde(i,b);
}
void Link(int x,int y) 
{
	++x,++y;
	if(!stage){
		adj[x].pb(y); adj[y].pb(x);
		uni(x,y);
		if(adj[y].size()>=3) swap(x,y);
		if(adj[x].size()>=3)
			stage=1, rebuild(x);
	}
	else{
		for(int j=0;j<4;++j)
			S[j].adde(x,y);
	}
}
int CountCritical(){
	if(!stage)
	{
		if(ps.size()>=2) return 0;
		if(ps.size()==0) return n;
		return sz[gf(ps[0])];
	}
	else
		return S[0].calc()+S[1].calc()+S[2].calc()+S[3].calc();
}

Subtask #1
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	29292 KB	Output is correct
2	Correct	22 ms	29676 KB	Output is correct
3	Correct	22 ms	29676 KB	Output is correct
4	Correct	20 ms	29420 KB	Output is correct
5	Correct	21 ms	29568 KB	Output is correct
6	Correct	23 ms	29548 KB	Output is correct
7	Correct	21 ms	29548 KB	Output is correct
8	Correct	22 ms	29548 KB	Output is correct
9	Correct	22 ms	29676 KB	Output is correct
10	Correct	22 ms	29676 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	450 ms	49772 KB	Output is correct
2	Correct	901 ms	74748 KB	Output is correct
3	Correct	1490 ms	69100 KB	Output is correct
4	Correct	1105 ms	68460 KB	Output is correct
5	Correct	1107 ms	68492 KB	Output is correct
6	Correct	1109 ms	67536 KB	Output is correct
7	Correct	1329 ms	69060 KB	Output is correct
8	Correct	1282 ms	92396 KB	Output is correct
9	Correct	1455 ms	99108 KB	Output is correct
10	Correct	729 ms	68076 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	29292 KB	Output is correct
2	Correct	22 ms	29676 KB	Output is correct
3	Correct	22 ms	29676 KB	Output is correct
4	Correct	20 ms	29420 KB	Output is correct
5	Correct	21 ms	29568 KB	Output is correct
6	Correct	23 ms	29548 KB	Output is correct
7	Correct	21 ms	29548 KB	Output is correct
8	Correct	22 ms	29548 KB	Output is correct
9	Correct	22 ms	29676 KB	Output is correct
10	Correct	22 ms	29676 KB	Output is correct
11	Correct	22 ms	29676 KB	Output is correct
12	Correct	25 ms	30060 KB	Output is correct
13	Correct	25 ms	30060 KB	Output is correct
14	Correct	25 ms	29804 KB	Output is correct
15	Correct	25 ms	30188 KB	Output is correct
16	Correct	26 ms	29804 KB	Output is correct
17	Correct	24 ms	29804 KB	Output is correct
18	Correct	24 ms	30316 KB	Output is correct
19	Correct	28 ms	29804 KB	Output is correct
20	Correct	26 ms	30060 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	29292 KB	Output is correct
2	Correct	22 ms	29676 KB	Output is correct
3	Correct	22 ms	29676 KB	Output is correct
4	Correct	20 ms	29420 KB	Output is correct
5	Correct	21 ms	29568 KB	Output is correct
6	Correct	23 ms	29548 KB	Output is correct
7	Correct	21 ms	29548 KB	Output is correct
8	Correct	22 ms	29548 KB	Output is correct
9	Correct	22 ms	29676 KB	Output is correct
10	Correct	22 ms	29676 KB	Output is correct
11	Correct	22 ms	29676 KB	Output is correct
12	Correct	25 ms	30060 KB	Output is correct
13	Correct	25 ms	30060 KB	Output is correct
14	Correct	25 ms	29804 KB	Output is correct
15	Correct	25 ms	30188 KB	Output is correct
16	Correct	26 ms	29804 KB	Output is correct
17	Correct	24 ms	29804 KB	Output is correct
18	Correct	24 ms	30316 KB	Output is correct
19	Correct	28 ms	29804 KB	Output is correct
20	Correct	26 ms	30060 KB	Output is correct
21	Correct	39 ms	30876 KB	Output is correct
22	Correct	61 ms	31596 KB	Output is correct
23	Correct	57 ms	32236 KB	Output is correct
24	Correct	65 ms	33004 KB	Output is correct
25	Correct	36 ms	33132 KB	Output is correct
26	Correct	64 ms	33408 KB	Output is correct
27	Correct	83 ms	33004 KB	Output is correct
28	Correct	56 ms	33004 KB	Output is correct
29	Correct	50 ms	33772 KB	Output is correct
30	Correct	79 ms	33260 KB	Output is correct

Subtask #5
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	29292 KB	Output is correct
2	Correct	22 ms	29676 KB	Output is correct
3	Correct	22 ms	29676 KB	Output is correct
4	Correct	20 ms	29420 KB	Output is correct
5	Correct	21 ms	29568 KB	Output is correct
6	Correct	23 ms	29548 KB	Output is correct
7	Correct	21 ms	29548 KB	Output is correct
8	Correct	22 ms	29548 KB	Output is correct
9	Correct	22 ms	29676 KB	Output is correct
10	Correct	22 ms	29676 KB	Output is correct
11	Correct	450 ms	49772 KB	Output is correct
12	Correct	901 ms	74748 KB	Output is correct
13	Correct	1490 ms	69100 KB	Output is correct
14	Correct	1105 ms	68460 KB	Output is correct
15	Correct	1107 ms	68492 KB	Output is correct
16	Correct	1109 ms	67536 KB	Output is correct
17	Correct	1329 ms	69060 KB	Output is correct
18	Correct	1282 ms	92396 KB	Output is correct
19	Correct	1455 ms	99108 KB	Output is correct
20	Correct	729 ms	68076 KB	Output is correct
21	Correct	22 ms	29676 KB	Output is correct
22	Correct	25 ms	30060 KB	Output is correct
23	Correct	25 ms	30060 KB	Output is correct
24	Correct	25 ms	29804 KB	Output is correct
25	Correct	25 ms	30188 KB	Output is correct
26	Correct	26 ms	29804 KB	Output is correct
27	Correct	24 ms	29804 KB	Output is correct
28	Correct	24 ms	30316 KB	Output is correct
29	Correct	28 ms	29804 KB	Output is correct
30	Correct	26 ms	30060 KB	Output is correct
31	Correct	39 ms	30876 KB	Output is correct
32	Correct	61 ms	31596 KB	Output is correct
33	Correct	57 ms	32236 KB	Output is correct
34	Correct	65 ms	33004 KB	Output is correct
35	Correct	36 ms	33132 KB	Output is correct
36	Correct	64 ms	33408 KB	Output is correct
37	Correct	83 ms	33004 KB	Output is correct
38	Correct	56 ms	33004 KB	Output is correct
39	Correct	50 ms	33772 KB	Output is correct
40	Correct	79 ms	33260 KB	Output is correct
41	Correct	236 ms	41980 KB	Output is correct
42	Correct	623 ms	74960 KB	Output is correct
43	Correct	343 ms	63980 KB	Output is correct
44	Correct	642 ms	66028 KB	Output is correct
45	Correct	968 ms	70508 KB	Output is correct
46	Correct	718 ms	62700 KB	Output is correct
47	Correct	963 ms	63468 KB	Output is correct
48	Correct	433 ms	70636 KB	Output is correct
49	Correct	708 ms	62956 KB	Output is correct
50	Correct	740 ms	62572 KB	Output is correct
51	Correct	295 ms	60524 KB	Output is correct
52	Correct	618 ms	59056 KB	Output is correct
53	Correct	414 ms	69868 KB	Output is correct
54	Correct	1061 ms	80492 KB	Output is correct
55	Correct	810 ms	64464 KB	Output is correct

Submission #351190

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