oj.uz

답안 #400728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400728 2021-05-08T15:19:01 Z Jasiekstrz 낙하산 고리들 (IOI12_rings) C++17
37 / 100
 1542 ms 129416 KB 
#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)
		{
			if(on_cycle[A] && on_cycle[B])
			{
				set<int> st;
				for(int v:{A,B})
				{
					if(ok.find(v)!=ok.end())
						st.insert(v);
				}
				ok=st;
			}
			else
				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 24128 KB Output is correct
3 Correct 16 ms 24112 KB Output is correct
4 Correct 14 ms 23892 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 24012 KB Output is correct
8 Correct 16 ms 24140 KB Output is correct
9 Correct 18 ms 24140 KB Output is correct
10 Correct 17 ms 24268 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 491 ms 66580 KB Output is correct
2 Correct 1049 ms 82612 KB Output is correct
3 Correct 1473 ms 79316 KB Output is correct
4 Correct 1416 ms 107652 KB Output is correct
5 Correct 1405 ms 108984 KB Output is correct
6 Correct 1542 ms 129416 KB Output is correct
7 Correct 1331 ms 79388 KB Output is correct
8 Correct 1273 ms 101980 KB Output is correct
9 Correct 1384 ms 109248 KB Output is correct
10 Correct 1113 ms 107204 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 16 ms 24128 KB Output is correct
3 Correct 16 ms 24112 KB Output is correct
4 Correct 14 ms 23892 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 24012 KB Output is correct
8 Correct 16 ms 24140 KB Output is correct
9 Correct 18 ms 24140 KB Output is correct
10 Correct 17 ms 24268 KB Output is correct
11 Correct 19 ms 24228 KB Output is correct
12 Correct 21 ms 24784 KB Output is correct
13 Correct 21 ms 24664 KB Output is correct
14 Incorrect 19 ms 24504 KB Output isn't correct
15 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 24128 KB Output is correct
3 Correct 16 ms 24112 KB Output is correct
4 Correct 14 ms 23892 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 24012 KB Output is correct
8 Correct 16 ms 24140 KB Output is correct
9 Correct 18 ms 24140 KB Output is correct
10 Correct 17 ms 24268 KB Output is correct
11 Correct 19 ms 24228 KB Output is correct
12 Correct 21 ms 24784 KB Output is correct
13 Correct 21 ms 24664 KB Output is correct
14 Incorrect 19 ms 24504 KB Output isn't correct
15 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 24128 KB Output is correct
3 Correct 16 ms 24112 KB Output is correct
4 Correct 14 ms 23892 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 24012 KB Output is correct
8 Correct 16 ms 24140 KB Output is correct
9 Correct 18 ms 24140 KB Output is correct
10 Correct 17 ms 24268 KB Output is correct
11 Correct 491 ms 66580 KB Output is correct
12 Correct 1049 ms 82612 KB Output is correct
13 Correct 1473 ms 79316 KB Output is correct
14 Correct 1416 ms 107652 KB Output is correct
15 Correct 1405 ms 108984 KB Output is correct
16 Correct 1542 ms 129416 KB Output is correct
17 Correct 1331 ms 79388 KB Output is correct
18 Correct 1273 ms 101980 KB Output is correct
19 Correct 1384 ms 109248 KB Output is correct
20 Correct 1113 ms 107204 KB Output is correct
21 Correct 19 ms 24228 KB Output is correct
22 Correct 21 ms 24784 KB Output is correct
23 Correct 21 ms 24664 KB Output is correct
24 Incorrect 19 ms 24504 KB Output isn't correct
25 Halted 0 ms 0 KB -