Submission #1015565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015565		parsadox2	Parachute rings (IOI12_rings)	C++17	100 / 100	1222 ms	231880 KiB

rings

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int ans , n , deg[N];
bool flg;
vector <int> adj[N];

struct Graph{
	int vert , par[N] , d[N];
	bool ok , marked[N];
	vector <int> all[N];
	void Dfs(int v , int p = -1)
	{
		marked[v] = true;
		par[v] = (p == -1 ? v : par[p]);
		int D = (p != -1);
		for(auto u : adj[v])  if(u != vert)
		{
			if(!marked[u])
			{
				D++;
				Dfs(u , v);
			}
			else if(u != p)
				ok = false;
		}
		if(D > 2)
			ok = false;
		d[v] = D;
	}
	int root(int v)
	{
		return (par[v] == v ? v : par[v] = root(par[v]));
	}
	void Build()
	{
		ok = true;
		marked[vert] = true;
		for(int i = 0 ; i < n ; i++)  if(!marked[i])
			Dfs(i);
	}
	void Add(int a , int b)
	{
		if(a == vert || b == vert)
			return;
		int ra = root(a) , rb = root(b);
		if(d[a] > 1 || d[b] > 1 || ra == rb)
		{
			ok = false;
			return;
		}
		par[rb] = ra;
		d[a]++;
		d[b]++;
	}
} graph[5];

struct DSU{
	int sz[N] , par[N];
	void Build()
	{
		for(int i = 0 ; i < n ; i++)
		{
			par[i] = i;
			sz[i] = 1;
		}
	}
	int root(int v)
	{
		return (par[v] == v ? v : par[v] = root(par[v]));
	}
	void Merge(int a , int b)
	{
		deg[a]++;  deg[b]++;
		adj[a].push_back(b);
		adj[b].push_back(a);
		if(deg[a] < deg[b])
			swap(a , b);
		int ra = root(a) , rb = root(b);
		//cout << a << " --- " << b << " " << ra << " " << rb << endl;
		if(deg[a] == 3)
		{
			graph[0].vert = a;
			for(int i = 1 ; i <= 3 ; i++)
				graph[i].vert = adj[a][i - 1];
			for(int i = 0 ; i < 4 ; i++)
				graph[i].Build();
			flg = true;
			return;
		}
		if(ra == rb)
		{
			ans = (ans == n ? sz[ra] : 0);
			return;
		}
		par[rb] = ra;
		sz[ra] += sz[rb];
	}
} dsu;

void Init(int x)
{
	n = x;
	ans = x;
	dsu.Build();
}

void Link(int a , int b)
{
	if(!flg)
		dsu.Merge(a , b);
	else
	{
		for(int i = 0 ; i < 4 ; i++)
			graph[i].Add(a , b);
	}
}

int CountCritical()
{
	if(!flg)
		return ans;
	else
	{
		int cnt = 0;
		for(int i = 0 ; i < 4 ; i++)
			cnt += graph[i].ok;
		return cnt;
	}
}

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