답안 #62489 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62489	2018-07-28T19:07:31 Z	zetapi	낙하산 고리들 (IOI12_rings)	C++14	100 / 100	2836 ms	93536 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=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;

void Init(int N_) 
{
	M=0;
  	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] 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++]=mp(X,Y);
	if(Quad==0)
	{
		vec[X].pb(Y);
		vec[Y].pb(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];
			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]);
}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	24 ms	24180 KB	Output is correct
3	Correct	24 ms	24216 KB	Output is correct
4	Correct	22 ms	24216 KB	Output is correct
5	Correct	22 ms	24216 KB	Output is correct
6	Correct	24 ms	24352 KB	Output is correct
7	Correct	23 ms	24352 KB	Output is correct
8	Correct	25 ms	24352 KB	Output is correct
9	Correct	24 ms	24428 KB	Output is correct
10	Correct	24 ms	24428 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	507 ms	48588 KB	Output is correct
2	Correct	1055 ms	69308 KB	Output is correct
3	Correct	384 ms	69308 KB	Output is correct
4	Correct	1342 ms	71184 KB	Output is correct
5	Correct	1304 ms	71184 KB	Output is correct
6	Correct	1442 ms	71184 KB	Output is correct
7	Correct	351 ms	71184 KB	Output is correct
8	Correct	2144 ms	87160 KB	Output is correct
9	Correct	2836 ms	93536 KB	Output is correct
10	Correct	896 ms	93536 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	24 ms	24180 KB	Output is correct
3	Correct	24 ms	24216 KB	Output is correct
4	Correct	22 ms	24216 KB	Output is correct
5	Correct	22 ms	24216 KB	Output is correct
6	Correct	24 ms	24352 KB	Output is correct
7	Correct	23 ms	24352 KB	Output is correct
8	Correct	25 ms	24352 KB	Output is correct
9	Correct	24 ms	24428 KB	Output is correct
10	Correct	24 ms	24428 KB	Output is correct
11	Correct	24 ms	93536 KB	Output is correct
12	Correct	29 ms	93536 KB	Output is correct
13	Correct	29 ms	93536 KB	Output is correct
14	Correct	24 ms	93536 KB	Output is correct
15	Correct	25 ms	93536 KB	Output is correct
16	Correct	26 ms	93536 KB	Output is correct
17	Correct	25 ms	93536 KB	Output is correct
18	Correct	27 ms	93536 KB	Output is correct
19	Correct	29 ms	93536 KB	Output is correct
20	Correct	29 ms	93536 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	24 ms	24180 KB	Output is correct
3	Correct	24 ms	24216 KB	Output is correct
4	Correct	22 ms	24216 KB	Output is correct
5	Correct	22 ms	24216 KB	Output is correct
6	Correct	24 ms	24352 KB	Output is correct
7	Correct	23 ms	24352 KB	Output is correct
8	Correct	25 ms	24352 KB	Output is correct
9	Correct	24 ms	24428 KB	Output is correct
10	Correct	24 ms	24428 KB	Output is correct
11	Correct	24 ms	93536 KB	Output is correct
12	Correct	29 ms	93536 KB	Output is correct
13	Correct	29 ms	93536 KB	Output is correct
14	Correct	24 ms	93536 KB	Output is correct
15	Correct	25 ms	93536 KB	Output is correct
16	Correct	26 ms	93536 KB	Output is correct
17	Correct	25 ms	93536 KB	Output is correct
18	Correct	27 ms	93536 KB	Output is correct
19	Correct	29 ms	93536 KB	Output is correct
20	Correct	29 ms	93536 KB	Output is correct
21	Correct	44 ms	93536 KB	Output is correct
22	Correct	56 ms	93536 KB	Output is correct
23	Correct	67 ms	93536 KB	Output is correct
24	Correct	54 ms	93536 KB	Output is correct
25	Correct	38 ms	93536 KB	Output is correct
26	Correct	54 ms	93536 KB	Output is correct
27	Correct	74 ms	93536 KB	Output is correct
28	Correct	54 ms	93536 KB	Output is correct
29	Correct	54 ms	93536 KB	Output is correct
30	Correct	91 ms	93536 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	24 ms	24180 KB	Output is correct
3	Correct	24 ms	24216 KB	Output is correct
4	Correct	22 ms	24216 KB	Output is correct
5	Correct	22 ms	24216 KB	Output is correct
6	Correct	24 ms	24352 KB	Output is correct
7	Correct	23 ms	24352 KB	Output is correct
8	Correct	25 ms	24352 KB	Output is correct
9	Correct	24 ms	24428 KB	Output is correct
10	Correct	24 ms	24428 KB	Output is correct
11	Correct	507 ms	48588 KB	Output is correct
12	Correct	1055 ms	69308 KB	Output is correct
13	Correct	384 ms	69308 KB	Output is correct
14	Correct	1342 ms	71184 KB	Output is correct
15	Correct	1304 ms	71184 KB	Output is correct
16	Correct	1442 ms	71184 KB	Output is correct
17	Correct	351 ms	71184 KB	Output is correct
18	Correct	2144 ms	87160 KB	Output is correct
19	Correct	2836 ms	93536 KB	Output is correct
20	Correct	896 ms	93536 KB	Output is correct
21	Correct	24 ms	93536 KB	Output is correct
22	Correct	29 ms	93536 KB	Output is correct
23	Correct	29 ms	93536 KB	Output is correct
24	Correct	24 ms	93536 KB	Output is correct
25	Correct	25 ms	93536 KB	Output is correct
26	Correct	26 ms	93536 KB	Output is correct
27	Correct	25 ms	93536 KB	Output is correct
28	Correct	27 ms	93536 KB	Output is correct
29	Correct	29 ms	93536 KB	Output is correct
30	Correct	29 ms	93536 KB	Output is correct
31	Correct	44 ms	93536 KB	Output is correct
32	Correct	56 ms	93536 KB	Output is correct
33	Correct	67 ms	93536 KB	Output is correct
34	Correct	54 ms	93536 KB	Output is correct
35	Correct	38 ms	93536 KB	Output is correct
36	Correct	54 ms	93536 KB	Output is correct
37	Correct	74 ms	93536 KB	Output is correct
38	Correct	54 ms	93536 KB	Output is correct
39	Correct	54 ms	93536 KB	Output is correct
40	Correct	91 ms	93536 KB	Output is correct
41	Correct	246 ms	93536 KB	Output is correct
42	Correct	930 ms	93536 KB	Output is correct
43	Correct	285 ms	93536 KB	Output is correct
44	Correct	363 ms	93536 KB	Output is correct
45	Correct	517 ms	93536 KB	Output is correct
46	Correct	825 ms	93536 KB	Output is correct
47	Correct	1192 ms	93536 KB	Output is correct
48	Correct	347 ms	93536 KB	Output is correct
49	Correct	827 ms	93536 KB	Output is correct
50	Correct	878 ms	93536 KB	Output is correct
51	Correct	260 ms	93536 KB	Output is correct
52	Correct	350 ms	93536 KB	Output is correct
53	Correct	288 ms	93536 KB	Output is correct
54	Correct	1503 ms	93536 KB	Output is correct
55	Correct	547 ms	93536 KB	Output is correct

답안 #62489

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