oj.uz

Submission #400720

# Submission time Handle Problem Language Result Execution time Memory
400720 2021-05-08T15:00:34 Z Jasiekstrz Parachute rings (IOI12_rings) C++17
0 / 100
 1049 ms 89192 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)
		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.empty())
			set_all(false);
		else if(!was_cycle)
		{
			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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Incorrect 16 ms 24140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 73412 KB Output is correct
2 Incorrect 1049 ms 89192 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Incorrect 16 ms 24140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Incorrect 16 ms 24140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Incorrect 16 ms 24140 KB Output isn't correct
3 Halted 0 ms 0 KB -