oj.uz

Submission #132462

# Submission time Handle Problem Language Result Execution time Memory
132462 2019-07-18T23:00:40 Z arthurconmy Parachute rings (IOI12_rings) C++14
0 / 100
 1403 ms 80248 KB 
/* Arthur Conmy / arthurconmy */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;

const int MAXN=1000001; 

// GENERAL

int n;
vector<int> adj[MAXN];
int deg[MAXN];
int v_max=0;
int d_max=0;

// DSU

int link[MAXN];
int sz[MAXN];
int no_cycles=0;
int cycle_size=-1;

// DFS

bool vis[MAXN];
int prior=-1;

bool dfs(int b4, int u)
{
	vis[u]=1;

	for(auto v:adj[u])
	{
		if(vis[v] && v!=b4) return false;
		if(vis[v]) continue;

		bool b = dfs(u,v);
		if(!b) return false;
	}

	return true;
}

int emp(int a)
{
	while(a!=link[a]) a=link[a];
	return a;
}

void join(int a, int b)
{
	a=emp(a);
	b=emp(b);
	if(a==b) return;

	if(sz[a]<sz[b]) swap(a,b);
	sz[a]+=sz[b];
	link[b]=a;
}

void Init(int N)
{
	n=N;

	for(int i=0; i<n; i++)
	{
		link[i]=i;
		sz[i]=1;
	}
}

void Link(int A, int B)
{
	adj[A].push_back(B);
	adj[B].push_back(A);

	deg[A]++;
	deg[B]++;
	if(deg[B]>deg[A]) swap(A,B);

	if(deg[A] > d_max)
	{
		d_max=deg[A]+1;
		v_max=A;
	}

	if(emp(A)==emp(B))
	{
		no_cycles++;
		cycle_size=sz[emp(A)];
	}

	join(A,B);
}

int CountCritical()
{
	if(d_max < 2)
	{
		return n;
	}

	if(d_max == 2)
	{
		if(no_cycles==0) return n;
		if(no_cycles>1) return 0;
		return cycle_size;
	}

	vector<int> trying = {v_max};

	if(d_max==3)
	{
		for(auto u:adj[v_max]) trying.push_back(u);
	}
	
	int no_that_work=0;
	
	for(auto v:trying)
	{
		for(int i=0; i<n; i++) vis[i]=0;
		bool works=1;

		for(auto u:adj[v])
		{
			deg[u]--;
		}

		for(int i=1; i<MAXN; i++)
		{
			if(i==v) continue;
			if(deg[i] > 2) works=0;
		}

		for(auto u:adj[v])
		{
			deg[u]++;
		}

		if(!works) continue;

		for(int i=0; i<n; i++)
		{
			if(vis[i]) continue;
			bool b2 = dfs(-1,i);
			if(!b2)
			{
				works=0;
				break;
			}
		}

		if(works) no_that_work++;
	}

	return no_that_work;
}

// void thing()
// {
// 	cout << CountCritical() << endl;
// }

// int main()
// {
// 	#ifdef ARTHUR_LOCAL
// 		ifstream cin("input.txt");
// 	#endif

// 	Init(6);
// 	thing();
// 	Link(0,1);
// 	thing();
// 	Link(1,2);
// 	thing();
// 	Link(2,0);
// 	thing();
// }

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23804 KB Output is correct
2 Correct 27 ms 24056 KB Output is correct
3 Correct 27 ms 24184 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 26 ms 24024 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Incorrect 27 ms 24188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 53112 KB Output is correct
2 Correct 1264 ms 69984 KB Output is correct
3 Correct 1263 ms 76552 KB Output is correct
4 Correct 1223 ms 80244 KB Output is correct
5 Correct 1231 ms 80248 KB Output is correct
6 Correct 1268 ms 78904 KB Output is correct
7 Correct 1297 ms 75476 KB Output is correct
8 Incorrect 1403 ms 77816 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23804 KB Output is correct
2 Correct 27 ms 24056 KB Output is correct
3 Correct 27 ms 24184 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 26 ms 24024 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Incorrect 27 ms 24188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23804 KB Output is correct
2 Correct 27 ms 24056 KB Output is correct
3 Correct 27 ms 24184 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 26 ms 24024 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Incorrect 27 ms 24188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23804 KB Output is correct
2 Correct 27 ms 24056 KB Output is correct
3 Correct 27 ms 24184 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 26 ms 24024 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Incorrect 27 ms 24188 KB Output isn't correct
10 Halted 0 ms 0 KB -