oj.uz

Submission #400782

# Submission time Handle Problem Language Result Execution time Memory
400782 2021-05-08T16:09:36 Z Jasiekstrz Parachute rings (IOI12_rings) C++17
37 / 100
 1570 ms 134420 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;
}
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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 17 ms 24172 KB Output is correct
3 Correct 17 ms 24156 KB Output is correct
4 Correct 15 ms 23884 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 24124 KB Output is correct
8 Correct 16 ms 24188 KB Output is correct
9 Correct 17 ms 24140 KB Output is correct
10 Correct 17 ms 24140 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 66776 KB Output is correct
2 Correct 1048 ms 82612 KB Output is correct
3 Correct 638 ms 79284 KB Output is correct
4 Correct 1397 ms 110148 KB Output is correct
5 Correct 1426 ms 113804 KB Output is correct
6 Correct 1570 ms 134420 KB Output is correct
7 Correct 630 ms 79420 KB Output is correct
8 Correct 1271 ms 102036 KB Output is correct
9 Correct 1380 ms 109272 KB Output is correct
10 Correct 1083 ms 108800 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 17 ms 24172 KB Output is correct
3 Correct 17 ms 24156 KB Output is correct
4 Correct 15 ms 23884 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 24124 KB Output is correct
8 Correct 16 ms 24188 KB Output is correct
9 Correct 17 ms 24140 KB Output is correct
10 Correct 17 ms 24140 KB Output is correct
11 Correct 17 ms 24180 KB Output is correct
12 Correct 21 ms 24716 KB Output is correct
13 Correct 22 ms 24648 KB Output is correct
14 Incorrect 20 ms 24544 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 17 ms 24172 KB Output is correct
3 Correct 17 ms 24156 KB Output is correct
4 Correct 15 ms 23884 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 24124 KB Output is correct
8 Correct 16 ms 24188 KB Output is correct
9 Correct 17 ms 24140 KB Output is correct
10 Correct 17 ms 24140 KB Output is correct
11 Correct 17 ms 24180 KB Output is correct
12 Correct 21 ms 24716 KB Output is correct
13 Correct 22 ms 24648 KB Output is correct
14 Incorrect 20 ms 24544 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 17 ms 24172 KB Output is correct
3 Correct 17 ms 24156 KB Output is correct
4 Correct 15 ms 23884 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 24124 KB Output is correct
8 Correct 16 ms 24188 KB Output is correct
9 Correct 17 ms 24140 KB Output is correct
10 Correct 17 ms 24140 KB Output is correct
11 Correct 498 ms 66776 KB Output is correct
12 Correct 1048 ms 82612 KB Output is correct
13 Correct 638 ms 79284 KB Output is correct
14 Correct 1397 ms 110148 KB Output is correct
15 Correct 1426 ms 113804 KB Output is correct
16 Correct 1570 ms 134420 KB Output is correct
17 Correct 630 ms 79420 KB Output is correct
18 Correct 1271 ms 102036 KB Output is correct
19 Correct 1380 ms 109272 KB Output is correct
20 Correct 1083 ms 108800 KB Output is correct
21 Correct 17 ms 24180 KB Output is correct
22 Correct 21 ms 24716 KB Output is correct
23 Correct 22 ms 24648 KB Output is correct
24 Incorrect 20 ms 24544 KB Output isn't correct
25 Halted 0 ms 0 KB -