Submission #62494

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
62494	2018-07-28T19:26:16 Z	zetapi	Parachute rings (IOI12_rings)	C++17	100 / 100	2695 ms	97452 KB

rings

#include <cstdio>
#include <vector>
#include <cassert>
 
 
using namespace std;
 
typedef pair<int,int>  pii;
 
const int MAX=1e6+99;
 
vector<int> vec[MAX];

pii E[MAX];

int linear[4],destruct[4],deg[4][MAX],OtherEnd[4][MAX];
 
int N,M,cnt,CycleSize,Quad,a,b,lol,size_[MAX];

void Init(int N_) 
{
	M=0;
  	N=N_;
  	cnt=0;
  	Quad=0;
  	CycleSize=0;
  	for(int A=0;A<N;A++)
  	{
  		size_[A]=1;
  		deg[0][A]=0;
  		OtherEnd[0][A]=A;
  		vec[A].clear();
  	}
  	return ;
}
 
void Add(int X,int Y)
{
	for(int A=0;A<4;A++) 	
	{
		if(!linear[A] or destruct[A]==X or destruct[A]==Y)
			continue;
		deg[A][X]++;
		deg[A][Y]++;
		if(deg[A][X]==3 or deg[A][Y]==3 or OtherEnd[A][X]==Y)
		{
			linear[A]=0;
			continue;
		}
		a=OtherEnd[A][X];
		b=OtherEnd[A][Y];
		OtherEnd[A][X]=-1;
		OtherEnd[A][Y]=-1;
		OtherEnd[A][a]=b;
		OtherEnd[A][b]=a;
	}
	return ;
}
 
void Split(int X)
{
	Quad=1;
	destruct[0]=X;
	destruct[1]=vec[X][0];
	destruct[2]=vec[X][1];
	destruct[3]=vec[X][2];
	for(int A=0;A<4;A++)
	{
		linear[A]=1;
		for(int B=0;B<N;B++)
		{
			deg[A][B]=0;
			OtherEnd[A][B]=B;
		}
	}
	for(int A=0;A<M;A++)
		Add(E[A].first,E[A].second);
	return ;	
}
 
void Link(int X,int Y) 
{
	E[M++]=make_pair(X,Y);
	if(Quad==0)
	{
		vec[X].push_back(Y);
		vec[Y].push_back(X);
		deg[0][X]++;
		deg[0][Y]++;
		if(deg[0][X]==3)
		{
			Split(X);
			return ;
		}
		if(deg[0][Y]==3)
		{
			Split(Y);
			return ;
		}
		if(OtherEnd[0][X]!=Y)
		{
          	a=OtherEnd[0][X];
			b=OtherEnd[0][Y];
			lol=size_[a];
          	size_[a]=lol+size_[b];
			size_[b]=lol+size_[b];
			OtherEnd[0][X]=-1;
			OtherEnd[0][Y]=-1;
			OtherEnd[0][a]=b;
			OtherEnd[0][b]=a;
			return ;
		}
		cnt++;
		if(cnt==1)
			CycleSize=size_[Y];
	}
	else
		Add(X,Y);
	return ;
}
 
int CountCritical() 
{	
	if(!Quad)
	{
		if(cnt>1)
			return 0;
		else if(CycleSize)
			return CycleSize;
		else
			return N;
	}
	else
		return (linear[0]+linear[1]+linear[2]+linear[3]);
}

Subtask #1
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	26 ms	24308 KB	Output is correct
3	Correct	23 ms	24452 KB	Output is correct
4	Correct	21 ms	24452 KB	Output is correct
5	Correct	22 ms	24452 KB	Output is correct
6	Correct	24 ms	24452 KB	Output is correct
7	Correct	22 ms	24452 KB	Output is correct
8	Correct	25 ms	24452 KB	Output is correct
9	Correct	25 ms	24452 KB	Output is correct
10	Correct	24 ms	24452 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	496 ms	50628 KB	Output is correct
2	Correct	1010 ms	72468 KB	Output is correct
3	Correct	373 ms	72468 KB	Output is correct
4	Correct	1442 ms	74952 KB	Output is correct
5	Correct	1470 ms	74952 KB	Output is correct
6	Correct	1390 ms	74952 KB	Output is correct
7	Correct	352 ms	74952 KB	Output is correct
8	Correct	2081 ms	90820 KB	Output is correct
9	Correct	2695 ms	97452 KB	Output is correct
10	Correct	936 ms	97452 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	26 ms	24308 KB	Output is correct
3	Correct	23 ms	24452 KB	Output is correct
4	Correct	21 ms	24452 KB	Output is correct
5	Correct	22 ms	24452 KB	Output is correct
6	Correct	24 ms	24452 KB	Output is correct
7	Correct	22 ms	24452 KB	Output is correct
8	Correct	25 ms	24452 KB	Output is correct
9	Correct	25 ms	24452 KB	Output is correct
10	Correct	24 ms	24452 KB	Output is correct
11	Correct	23 ms	97452 KB	Output is correct
12	Correct	27 ms	97452 KB	Output is correct
13	Correct	28 ms	97452 KB	Output is correct
14	Correct	24 ms	97452 KB	Output is correct
15	Correct	24 ms	97452 KB	Output is correct
16	Correct	29 ms	97452 KB	Output is correct
17	Correct	24 ms	97452 KB	Output is correct
18	Correct	26 ms	97452 KB	Output is correct
19	Correct	27 ms	97452 KB	Output is correct
20	Correct	28 ms	97452 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	26 ms	24308 KB	Output is correct
3	Correct	23 ms	24452 KB	Output is correct
4	Correct	21 ms	24452 KB	Output is correct
5	Correct	22 ms	24452 KB	Output is correct
6	Correct	24 ms	24452 KB	Output is correct
7	Correct	22 ms	24452 KB	Output is correct
8	Correct	25 ms	24452 KB	Output is correct
9	Correct	25 ms	24452 KB	Output is correct
10	Correct	24 ms	24452 KB	Output is correct
11	Correct	23 ms	97452 KB	Output is correct
12	Correct	27 ms	97452 KB	Output is correct
13	Correct	28 ms	97452 KB	Output is correct
14	Correct	24 ms	97452 KB	Output is correct
15	Correct	24 ms	97452 KB	Output is correct
16	Correct	29 ms	97452 KB	Output is correct
17	Correct	24 ms	97452 KB	Output is correct
18	Correct	26 ms	97452 KB	Output is correct
19	Correct	27 ms	97452 KB	Output is correct
20	Correct	28 ms	97452 KB	Output is correct
21	Correct	42 ms	97452 KB	Output is correct
22	Correct	61 ms	97452 KB	Output is correct
23	Correct	63 ms	97452 KB	Output is correct
24	Correct	52 ms	97452 KB	Output is correct
25	Correct	36 ms	97452 KB	Output is correct
26	Correct	54 ms	97452 KB	Output is correct
27	Correct	75 ms	97452 KB	Output is correct
28	Correct	52 ms	97452 KB	Output is correct
29	Correct	50 ms	97452 KB	Output is correct
30	Correct	79 ms	97452 KB	Output is correct

Subtask #5
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	26 ms	24308 KB	Output is correct
3	Correct	23 ms	24452 KB	Output is correct
4	Correct	21 ms	24452 KB	Output is correct
5	Correct	22 ms	24452 KB	Output is correct
6	Correct	24 ms	24452 KB	Output is correct
7	Correct	22 ms	24452 KB	Output is correct
8	Correct	25 ms	24452 KB	Output is correct
9	Correct	25 ms	24452 KB	Output is correct
10	Correct	24 ms	24452 KB	Output is correct
11	Correct	496 ms	50628 KB	Output is correct
12	Correct	1010 ms	72468 KB	Output is correct
13	Correct	373 ms	72468 KB	Output is correct
14	Correct	1442 ms	74952 KB	Output is correct
15	Correct	1470 ms	74952 KB	Output is correct
16	Correct	1390 ms	74952 KB	Output is correct
17	Correct	352 ms	74952 KB	Output is correct
18	Correct	2081 ms	90820 KB	Output is correct
19	Correct	2695 ms	97452 KB	Output is correct
20	Correct	936 ms	97452 KB	Output is correct
21	Correct	23 ms	97452 KB	Output is correct
22	Correct	27 ms	97452 KB	Output is correct
23	Correct	28 ms	97452 KB	Output is correct
24	Correct	24 ms	97452 KB	Output is correct
25	Correct	24 ms	97452 KB	Output is correct
26	Correct	29 ms	97452 KB	Output is correct
27	Correct	24 ms	97452 KB	Output is correct
28	Correct	26 ms	97452 KB	Output is correct
29	Correct	27 ms	97452 KB	Output is correct
30	Correct	28 ms	97452 KB	Output is correct
31	Correct	42 ms	97452 KB	Output is correct
32	Correct	61 ms	97452 KB	Output is correct
33	Correct	63 ms	97452 KB	Output is correct
34	Correct	52 ms	97452 KB	Output is correct
35	Correct	36 ms	97452 KB	Output is correct
36	Correct	54 ms	97452 KB	Output is correct
37	Correct	75 ms	97452 KB	Output is correct
38	Correct	52 ms	97452 KB	Output is correct
39	Correct	50 ms	97452 KB	Output is correct
40	Correct	79 ms	97452 KB	Output is correct
41	Correct	262 ms	97452 KB	Output is correct
42	Correct	929 ms	97452 KB	Output is correct
43	Correct	289 ms	97452 KB	Output is correct
44	Correct	369 ms	97452 KB	Output is correct
45	Correct	526 ms	97452 KB	Output is correct
46	Correct	932 ms	97452 KB	Output is correct
47	Correct	1252 ms	97452 KB	Output is correct
48	Correct	313 ms	97452 KB	Output is correct
49	Correct	872 ms	97452 KB	Output is correct
50	Correct	933 ms	97452 KB	Output is correct
51	Correct	256 ms	97452 KB	Output is correct
52	Correct	320 ms	97452 KB	Output is correct
53	Correct	295 ms	97452 KB	Output is correct
54	Correct	1482 ms	97452 KB	Output is correct
55	Correct	513 ms	97452 KB	Output is correct

Submission #62494

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