제출 #400782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
400782		Jasiekstrz	낙하산 고리들 (IOI12_rings)	C++17	37 / 100	1570 ms	134420 KiB

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];
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;
}
bool are_ngh(int x,int y)
{
	for(auto v:e[x])
	{
		if(v==y)
			return true;
	}
	return false;
}
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(ok.empty())
		return;
	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(pp[A]==pp[B])
				{
					if(ok.find(pp[A])!=ok.end())
					{
						ok.clear();
						ok.insert(pp[A]);
					}
					else
						ok.clear();
				}
				else if(are_ngh(pp[A],pp[B]))
				{
					set<int> st;
					for(int v:{pp[A],pp[B]})
					{
						if(ok.find(v)!=ok.end())
							st.insert(v);
					}
					ok=st;
				}
				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 / 20
• Subtask 2: 17 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31