oj.uz

Submission #400724

# Submission time Handle Problem Language Result Execution time Memory
400724 2021-05-08T15:06:05 Z Jasiekstrz Parachute rings (IOI12_rings) C++17
37 / 100
 1508 ms 142284 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)
			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

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 16 ms 24140 KB Output is correct
3 Correct 17 ms 24224 KB Output is correct
4 Correct 14 ms 23884 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 24140 KB Output is correct
8 Correct 16 ms 24140 KB Output is correct
9 Correct 17 ms 24196 KB Output is correct
10 Correct 16 ms 24272 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 66584 KB Output is correct
2 Correct 1045 ms 82612 KB Output is correct
3 Correct 1361 ms 88664 KB Output is correct
4 Correct 1380 ms 121028 KB Output is correct
5 Correct 1400 ms 122356 KB Output is correct
6 Correct 1508 ms 142284 KB Output is correct
7 Correct 1312 ms 88796 KB Output is correct
8 Correct 1266 ms 110852 KB Output is correct
9 Correct 1366 ms 120424 KB Output is correct
10 Correct 1140 ms 119932 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 16 ms 24140 KB Output is correct
3 Correct 17 ms 24224 KB Output is correct
4 Correct 14 ms 23884 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 24140 KB Output is correct
8 Correct 16 ms 24140 KB Output is correct
9 Correct 17 ms 24196 KB Output is correct
10 Correct 16 ms 24272 KB Output is correct
11 Incorrect 17 ms 24232 KB Output isn't correct
12 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 Correct 16 ms 24140 KB Output is correct
3 Correct 17 ms 24224 KB Output is correct
4 Correct 14 ms 23884 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 24140 KB Output is correct
8 Correct 16 ms 24140 KB Output is correct
9 Correct 17 ms 24196 KB Output is correct
10 Correct 16 ms 24272 KB Output is correct
11 Incorrect 17 ms 24232 KB Output isn't correct
12 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 Correct 16 ms 24140 KB Output is correct
3 Correct 17 ms 24224 KB Output is correct
4 Correct 14 ms 23884 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 24140 KB Output is correct
8 Correct 16 ms 24140 KB Output is correct
9 Correct 17 ms 24196 KB Output is correct
10 Correct 16 ms 24272 KB Output is correct
11 Correct 487 ms 66584 KB Output is correct
12 Correct 1045 ms 82612 KB Output is correct
13 Correct 1361 ms 88664 KB Output is correct
14 Correct 1380 ms 121028 KB Output is correct
15 Correct 1400 ms 122356 KB Output is correct
16 Correct 1508 ms 142284 KB Output is correct
17 Correct 1312 ms 88796 KB Output is correct
18 Correct 1266 ms 110852 KB Output is correct
19 Correct 1366 ms 120424 KB Output is correct
20 Correct 1140 ms 119932 KB Output is correct
21 Incorrect 17 ms 24232 KB Output isn't correct
22 Halted 0 ms 0 KB -