Submission #132463

#	Time	Username	Problem	Language	Result	Execution time	Memory
132463		arthurconmy	Parachute rings (IOI12_rings)	C++14	55 / 100	4019 ms	81908 KiB

rings

/* 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 cur_ignore=-1;

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

	for(auto v:adj[u])
	{
		if(v==cur_ignore) continue;
		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];
		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)
	{
		// cout << v << endl;

		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;

		// cout << works << endl;

		cur_ignore = v;

		for(int i=0; i<n; i++)
		{
			if(i==cur_ignore) continue;
			if(vis[i]) continue;
			bool b2 = dfs(-1,i);
			// cout << v << " " << i << " " << b2 << endl;
			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(7);
// 	Link(1,2);
// 	Link(2,3);
// 	Link(2,0);
// 	Link(0,5);
// 	Link(3,5);
// 	Link(3,4);
// 	thing();
// }

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31