Submission #62480

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
62480	2018-07-28T18:29:33 Z	zetapi	Parachute rings (IOI12_rings)	C++14	100 / 100	1952 ms	109508 KB

rings

#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define ll long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=2e6;

vector<int> vec[MAX];

int linear[4],destruct[4],deg[4][MAX],OtherEnd[4][MAX];

int N,cnt,CycleSize,Quad,a,b;

void Init(int N_) 
{
  	N=N_;
  	cnt=0;
  	Quad=0;
  	CycleSize=0;
  	for(int A=0;A<N;A++)
  	{
  		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])
			continue;
		if(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)
{
	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<N;A++)
		for(auto B:vec[A])
			if(A<B)
				Add(A,B);
	return ;	
}

void Link(int X,int Y) 
{
	a=X;
	b=Y;
	if(Quad==0)
	{
		vec[X].pb(Y);
		vec[Y].pb(X);
		deg[0][X]++;
		deg[0][Y]++;
		if(deg[0][X]==3)
		{
			Quad=1;
			Split(X);
			return ;
		}
		if(deg[0][Y]==3)
		{
			Quad=1;
			Split(Y);
			return ;
		}
		if(OtherEnd[0][X]!=Y)
		{
			a=OtherEnd[0][X];
			b=OtherEnd[0][Y];
			OtherEnd[0][X]=-1;
			OtherEnd[0][Y]=-1;
			OtherEnd[0][a]=b;
			OtherEnd[0][b]=a;
			return ;
		}
		cnt++;
		if(cnt==1)
		{
			int cur=X,pre=X;
			do
			{
      
				CycleSize++;
				if(vec[cur][0]==pre)
				{
					pre=cur;
					cur=vec[cur][1];
				}
				else
				{
					pre=cur;
					cur=vec[cur][0];
				}
			}
			while(cur!=X);
		}
	}
	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]);
}

/*signed main()
{
	ios_base::sync_with_stdio(false);

	Init(7);
	cout<<CountCritical()<<"\n";
	Link(1,2);
	cout<<CountCritical()<<"\n";
	Link(0,5);
	cout<<CountCritical()<<"\n";
	Link(2,0);
	cout<<CountCritical()<<"\n";
	Link(3,2);
	cout<<CountCritical()<<"\n";
	Link(3,5);
	cout<<CountCritical()<<"\n";
	Link(4,3);
	cout<<CountCritical()<<"\n";
	return 0;
}*/

Subtask #1
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	47352 KB	Output is correct
2	Correct	43 ms	47740 KB	Output is correct
3	Correct	43 ms	47756 KB	Output is correct
4	Correct	43 ms	47756 KB	Output is correct
5	Correct	49 ms	47756 KB	Output is correct
6	Correct	49 ms	47756 KB	Output is correct
7	Correct	44 ms	47796 KB	Output is correct
8	Correct	44 ms	47796 KB	Output is correct
9	Correct	44 ms	47812 KB	Output is correct
10	Correct	45 ms	47812 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	492 ms	67908 KB	Output is correct
2	Correct	787 ms	86596 KB	Output is correct
3	Correct	408 ms	86596 KB	Output is correct
4	Correct	1263 ms	86792 KB	Output is correct
5	Correct	1330 ms	86792 KB	Output is correct
6	Correct	1464 ms	86792 KB	Output is correct
7	Correct	370 ms	86792 KB	Output is correct
8	Correct	1574 ms	103328 KB	Output is correct
9	Correct	1952 ms	109508 KB	Output is correct
10	Correct	831 ms	109508 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	47352 KB	Output is correct
2	Correct	43 ms	47740 KB	Output is correct
3	Correct	43 ms	47756 KB	Output is correct
4	Correct	43 ms	47756 KB	Output is correct
5	Correct	49 ms	47756 KB	Output is correct
6	Correct	49 ms	47756 KB	Output is correct
7	Correct	44 ms	47796 KB	Output is correct
8	Correct	44 ms	47796 KB	Output is correct
9	Correct	44 ms	47812 KB	Output is correct
10	Correct	45 ms	47812 KB	Output is correct
11	Correct	44 ms	109508 KB	Output is correct
12	Correct	46 ms	109508 KB	Output is correct
13	Correct	46 ms	109508 KB	Output is correct
14	Correct	43 ms	109508 KB	Output is correct
15	Correct	45 ms	109508 KB	Output is correct
16	Correct	47 ms	109508 KB	Output is correct
17	Correct	45 ms	109508 KB	Output is correct
18	Correct	47 ms	109508 KB	Output is correct
19	Correct	49 ms	109508 KB	Output is correct
20	Correct	48 ms	109508 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	47352 KB	Output is correct
2	Correct	43 ms	47740 KB	Output is correct
3	Correct	43 ms	47756 KB	Output is correct
4	Correct	43 ms	47756 KB	Output is correct
5	Correct	49 ms	47756 KB	Output is correct
6	Correct	49 ms	47756 KB	Output is correct
7	Correct	44 ms	47796 KB	Output is correct
8	Correct	44 ms	47796 KB	Output is correct
9	Correct	44 ms	47812 KB	Output is correct
10	Correct	45 ms	47812 KB	Output is correct
11	Correct	44 ms	109508 KB	Output is correct
12	Correct	46 ms	109508 KB	Output is correct
13	Correct	46 ms	109508 KB	Output is correct
14	Correct	43 ms	109508 KB	Output is correct
15	Correct	45 ms	109508 KB	Output is correct
16	Correct	47 ms	109508 KB	Output is correct
17	Correct	45 ms	109508 KB	Output is correct
18	Correct	47 ms	109508 KB	Output is correct
19	Correct	49 ms	109508 KB	Output is correct
20	Correct	48 ms	109508 KB	Output is correct
21	Correct	65 ms	109508 KB	Output is correct
22	Correct	86 ms	109508 KB	Output is correct
23	Correct	85 ms	109508 KB	Output is correct
24	Correct	75 ms	109508 KB	Output is correct
25	Correct	57 ms	109508 KB	Output is correct
26	Correct	74 ms	109508 KB	Output is correct
27	Correct	97 ms	109508 KB	Output is correct
28	Correct	73 ms	109508 KB	Output is correct
29	Correct	71 ms	109508 KB	Output is correct
30	Correct	106 ms	109508 KB	Output is correct

Subtask #5
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	47352 KB	Output is correct
2	Correct	43 ms	47740 KB	Output is correct
3	Correct	43 ms	47756 KB	Output is correct
4	Correct	43 ms	47756 KB	Output is correct
5	Correct	49 ms	47756 KB	Output is correct
6	Correct	49 ms	47756 KB	Output is correct
7	Correct	44 ms	47796 KB	Output is correct
8	Correct	44 ms	47796 KB	Output is correct
9	Correct	44 ms	47812 KB	Output is correct
10	Correct	45 ms	47812 KB	Output is correct
11	Correct	492 ms	67908 KB	Output is correct
12	Correct	787 ms	86596 KB	Output is correct
13	Correct	408 ms	86596 KB	Output is correct
14	Correct	1263 ms	86792 KB	Output is correct
15	Correct	1330 ms	86792 KB	Output is correct
16	Correct	1464 ms	86792 KB	Output is correct
17	Correct	370 ms	86792 KB	Output is correct
18	Correct	1574 ms	103328 KB	Output is correct
19	Correct	1952 ms	109508 KB	Output is correct
20	Correct	831 ms	109508 KB	Output is correct
21	Correct	44 ms	109508 KB	Output is correct
22	Correct	46 ms	109508 KB	Output is correct
23	Correct	46 ms	109508 KB	Output is correct
24	Correct	43 ms	109508 KB	Output is correct
25	Correct	45 ms	109508 KB	Output is correct
26	Correct	47 ms	109508 KB	Output is correct
27	Correct	45 ms	109508 KB	Output is correct
28	Correct	47 ms	109508 KB	Output is correct
29	Correct	49 ms	109508 KB	Output is correct
30	Correct	48 ms	109508 KB	Output is correct
31	Correct	65 ms	109508 KB	Output is correct
32	Correct	86 ms	109508 KB	Output is correct
33	Correct	85 ms	109508 KB	Output is correct
34	Correct	75 ms	109508 KB	Output is correct
35	Correct	57 ms	109508 KB	Output is correct
36	Correct	74 ms	109508 KB	Output is correct
37	Correct	97 ms	109508 KB	Output is correct
38	Correct	73 ms	109508 KB	Output is correct
39	Correct	71 ms	109508 KB	Output is correct
40	Correct	106 ms	109508 KB	Output is correct
41	Correct	263 ms	109508 KB	Output is correct
42	Correct	824 ms	109508 KB	Output is correct
43	Correct	280 ms	109508 KB	Output is correct
44	Correct	369 ms	109508 KB	Output is correct
45	Correct	505 ms	109508 KB	Output is correct
46	Correct	796 ms	109508 KB	Output is correct
47	Correct	1198 ms	109508 KB	Output is correct
48	Correct	359 ms	109508 KB	Output is correct
49	Correct	818 ms	109508 KB	Output is correct
50	Correct	903 ms	109508 KB	Output is correct
51	Correct	273 ms	109508 KB	Output is correct
52	Correct	344 ms	109508 KB	Output is correct
53	Correct	319 ms	109508 KB	Output is correct
54	Correct	1550 ms	109508 KB	Output is correct
55	Correct	538 ms	109508 KB	Output is correct

Submission #62480

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