oj.uz

답안 #400766

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400766 2021-05-08T15:58:54 Z Jasiekstrz 낙하산 고리들 (IOI12_rings) C++17
37 / 100
 1582 ms 134212 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];
bool vis2[N+10];
int pp[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 dfs2(int x,int id)
{
	vis2[x]=true;
	pp[x]=id;
	for(auto v:e[x])
	{
		if(vis2[v] || on_cycle[v])
			continue;
		dfs2(v,id);
	}
	return;
}
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 if(vis2[A] && vis2[B] && pp[A]==pp[B])
			{
				if(ok.find(pp[A])!=ok.end())
				{
					ok.clear();
					ok.insert(pp[A]);
				}
				else
					ok.clear();
			}
			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);
			}
			for(int i=0;i<n;i++)
			{
				if(on_cycle[i])
					dfs2(i,i);
			}
		}
	}
	u(A,B);
	e[A].push_back(B);
	e[B].push_back(A);
	if(vis2[A] && !vis2[B])
		dfs2(B,pp[A]);
	if(vis2[B] && !vis2[A])
		dfs2(A,pp[B]);
	check_deg(A);
	check_deg(B);
	return;
}
int CountCritical()
{
	return ok.size();
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 19 ms 24140 KB Output is correct
3 Correct 17 ms 24192 KB Output is correct
4 Correct 15 ms 23888 KB Output is correct
5 Correct 16 ms 24140 KB Output is correct
6 Correct 18 ms 24392 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 18 ms 24164 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 490 ms 66628 KB Output is correct
2 Correct 1047 ms 82668 KB Output is correct
3 Correct 1582 ms 80972 KB Output is correct
4 Correct 1417 ms 110120 KB Output is correct
5 Correct 1403 ms 113860 KB Output is correct
6 Correct 1557 ms 134212 KB Output is correct
7 Correct 1576 ms 81664 KB Output is correct
8 Correct 1283 ms 101928 KB Output is correct
9 Correct 1397 ms 109244 KB Output is correct
10 Correct 1085 ms 110020 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 19 ms 24140 KB Output is correct
3 Correct 17 ms 24192 KB Output is correct
4 Correct 15 ms 23888 KB Output is correct
5 Correct 16 ms 24140 KB Output is correct
6 Correct 18 ms 24392 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 18 ms 24164 KB Output is correct
11 Correct 19 ms 24168 KB Output is correct
12 Correct 23 ms 24940 KB Output is correct
13 Correct 23 ms 24908 KB Output is correct
14 Incorrect 20 ms 24524 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 19 ms 24140 KB Output is correct
3 Correct 17 ms 24192 KB Output is correct
4 Correct 15 ms 23888 KB Output is correct
5 Correct 16 ms 24140 KB Output is correct
6 Correct 18 ms 24392 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 18 ms 24164 KB Output is correct
11 Correct 19 ms 24168 KB Output is correct
12 Correct 23 ms 24940 KB Output is correct
13 Correct 23 ms 24908 KB Output is correct
14 Incorrect 20 ms 24524 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 19 ms 24140 KB Output is correct
3 Correct 17 ms 24192 KB Output is correct
4 Correct 15 ms 23888 KB Output is correct
5 Correct 16 ms 24140 KB Output is correct
6 Correct 18 ms 24392 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 18 ms 24164 KB Output is correct
11 Correct 490 ms 66628 KB Output is correct
12 Correct 1047 ms 82668 KB Output is correct
13 Correct 1582 ms 80972 KB Output is correct
14 Correct 1417 ms 110120 KB Output is correct
15 Correct 1403 ms 113860 KB Output is correct
16 Correct 1557 ms 134212 KB Output is correct
17 Correct 1576 ms 81664 KB Output is correct
18 Correct 1283 ms 101928 KB Output is correct
19 Correct 1397 ms 109244 KB Output is correct
20 Correct 1085 ms 110020 KB Output is correct
21 Correct 19 ms 24168 KB Output is correct
22 Correct 23 ms 24940 KB Output is correct
23 Correct 23 ms 24908 KB Output is correct
24 Incorrect 20 ms 24524 KB Output isn't correct
25 Halted 0 ms 0 KB -