답안 #400724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
400724	2021-05-08T15:06:05 Z	Jasiekstrz	낙하산 고리들 (IOI12_rings)	C++17	37 / 100	1508 ms	142284 KB

rings

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n;
bool was_cycle;
set<int> ok;
vector<int> e[N+10];
int fau[N+10];
bool on_cycle[N+10];
bool vis[N+10];
int f(int x)
{
	if(fau[x]!=x)
		fau[x]=f(fau[x]);
	return fau[x];
}
void u(int x,int y)
{
	fau[f(y)]=f(x);
	return;
}
void set_all(bool c)
{
	ok.clear();
	if(c)
	{
		for(int i=0;i<n;i++)
			ok.insert(i);
	}
	return;
}
bool dfs(int x,int y)
{
	if(x==y)
	{
		on_cycle[x]=true;
		return true;
	}
	vis[x]=true;
	for(auto v:e[x])
	{
		if(!vis[v] && dfs(v,y))
		{
			on_cycle[x]=true;
			return true;
		}
	}
	return false;
}
void check_deg(int x)
{
	if(ok.empty())
		return;
	if(e[x].size()>3)
	{
		if(ok.find(x)!=ok.end())
		{
			ok.clear();
			ok.insert(x);
		}
		else
			ok.clear();
	}
	else if(e[x].size()==3)
	{
		vector<int> trash;
		set<int> ee={x,e[x][0],e[x][1],e[x][2]};
		for(auto v:ok)
		{
			if(ee.find(v)==ee.end())
				trash.push_back(v);
		}
		for(auto v:trash)
			ok.erase(v);
	}
	return;
}
void Init(int _N)
{
	n=_N;
	set_all(true);
	for(int i=0;i<n;i++)
		fau[i]=i;
	was_cycle=false;
	return;
}
void Link(int A,int B)
{
	if(f(A)==f(B))
	{
		if(was_cycle)
			ok.clear();
		else
		{
			was_cycle=true;
			dfs(A,B);
			for(int i=0;i<n;i++)
			{
				if(ok.find(i)!=ok.end() && !on_cycle[i])
					ok.erase(i);
			}
		}
	}
	u(A,B);
	e[A].push_back(B);
	e[B].push_back(A);
	check_deg(A);
	check_deg(B);
	return;
}
int CountCritical()
{
	return ok.size();
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	23756 KB	Output is correct
2	Correct	16 ms	24140 KB	Output is correct
3	Correct	17 ms	24224 KB	Output is correct
4	Correct	14 ms	23884 KB	Output is correct
5	Correct	16 ms	24064 KB	Output is correct
6	Correct	17 ms	24396 KB	Output is correct
7	Correct	15 ms	24140 KB	Output is correct
8	Correct	16 ms	24140 KB	Output is correct
9	Correct	17 ms	24196 KB	Output is correct
10	Correct	16 ms	24272 KB	Output is correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	487 ms	66584 KB	Output is correct
2	Correct	1045 ms	82612 KB	Output is correct
3	Correct	1361 ms	88664 KB	Output is correct
4	Correct	1380 ms	121028 KB	Output is correct
5	Correct	1400 ms	122356 KB	Output is correct
6	Correct	1508 ms	142284 KB	Output is correct
7	Correct	1312 ms	88796 KB	Output is correct
8	Correct	1266 ms	110852 KB	Output is correct
9	Correct	1366 ms	120424 KB	Output is correct
10	Correct	1140 ms	119932 KB	Output is correct

Subtask #3

0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	23756 KB	Output is correct
2	Correct	16 ms	24140 KB	Output is correct
3	Correct	17 ms	24224 KB	Output is correct
4	Correct	14 ms	23884 KB	Output is correct
5	Correct	16 ms	24064 KB	Output is correct
6	Correct	17 ms	24396 KB	Output is correct
7	Correct	15 ms	24140 KB	Output is correct
8	Correct	16 ms	24140 KB	Output is correct
9	Correct	17 ms	24196 KB	Output is correct
10	Correct	16 ms	24272 KB	Output is correct
11	Incorrect	17 ms	24232 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	23756 KB	Output is correct
2	Correct	16 ms	24140 KB	Output is correct
3	Correct	17 ms	24224 KB	Output is correct
4	Correct	14 ms	23884 KB	Output is correct
5	Correct	16 ms	24064 KB	Output is correct
6	Correct	17 ms	24396 KB	Output is correct
7	Correct	15 ms	24140 KB	Output is correct
8	Correct	16 ms	24140 KB	Output is correct
9	Correct	17 ms	24196 KB	Output is correct
10	Correct	16 ms	24272 KB	Output is correct
11	Incorrect	17 ms	24232 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	23756 KB	Output is correct
2	Correct	16 ms	24140 KB	Output is correct
3	Correct	17 ms	24224 KB	Output is correct
4	Correct	14 ms	23884 KB	Output is correct
5	Correct	16 ms	24064 KB	Output is correct
6	Correct	17 ms	24396 KB	Output is correct
7	Correct	15 ms	24140 KB	Output is correct
8	Correct	16 ms	24140 KB	Output is correct
9	Correct	17 ms	24196 KB	Output is correct
10	Correct	16 ms	24272 KB	Output is correct
11	Correct	487 ms	66584 KB	Output is correct
12	Correct	1045 ms	82612 KB	Output is correct
13	Correct	1361 ms	88664 KB	Output is correct
14	Correct	1380 ms	121028 KB	Output is correct
15	Correct	1400 ms	122356 KB	Output is correct
16	Correct	1508 ms	142284 KB	Output is correct
17	Correct	1312 ms	88796 KB	Output is correct
18	Correct	1266 ms	110852 KB	Output is correct
19	Correct	1366 ms	120424 KB	Output is correct
20	Correct	1140 ms	119932 KB	Output is correct
21	Incorrect	17 ms	24232 KB	Output isn't correct
22	Halted	0 ms	0 KB	-