Submission #415917

#	Time	Username	Problem	Language	Result	Execution time	Memory
415917		arayi	Parachute rings (IOI12_rings)	C++17	100 / 100	2606 ms	115264 KiB

rings

#include <cassert>
#include <vector>
#define ad push_back
#define MP make_pair
#define fr first
#define sc second
using namespace std;

const int N = 1e6 + 30;
vector<int> g[N], fp;
vector<pair<int, int> > m;
int p[N], sz[N], col[N], v[4][N], pr[4][N];
int n, mx, ans;

int gp(int x)
{
	if (p[x] == x) return x;
	return p[x] = gp(p[x]);
}
int gp(int i1, int x)
{
	if (pr[i1][x] == x) return x;
	return pr[i1][x] = gp(i1, pr[i1][x]);
}
void edge(int a, int b, int i1)
{
	if (a == fp[i1] || b == fp[i1]) return;
	v[i1][a]++, v[i1][b]++;
	if (gp(i1, a) == gp(i1, b) || v[i1][a] > 2 || v[i1][b] > 2) col[i1] = 1;
	pr[i1][gp(i1, b)] = gp(i1, a);
}
void Init(int N_) 
{
	n = N_;
	for (int i = 1; i <= n; i++)
	{
		p[i] = i, sz[i] = 1;
		for (int j = 0; j < 4; j++) pr[j][i] = i;
	}
}

void Link(int A, int B) 
{
	A++, B++;
	g[A].ad(B);
	g[B].ad(A);
	m.ad(MP(A, B));
	if (mx <= 2)
	{
		mx = max(mx, max((int)g[A].size(), (int)g[B].size()));
		if (g[B].size() > g[A].size()) swap(A, B);
		if (mx >= 3)
		{
			fp.ad(A);
			for (auto p : g[A]) fp.ad(p);
			assert((int)fp.size() == 4);
			for (auto p : m) 
				for (int i = 0; i < 4; i++)
					edge(p.fr, p.sc, i);
			return;
		}
		if (gp(A) == gp(B))
		{
			if (ans == 0) ans = sz[gp(A)];
			else ans = -1;
		}
		else
		{
			sz[gp(A)] += sz[gp(B)];
			p[gp(B)] = gp(A);
		}
	}
	else
		for (int i = 0; i < 4; i++)
			edge(A, B, i);
}

int CountCritical() 
{
	if (mx <= 2)
	{
		if (ans == -1) return 0;
		else if (ans == 0) return n;
		else return ans;
	}
	else
	{
		int ret = 0;
		for (int i = 0; i < 4; i++) if (!col[i]) ret++;
		return ret;
	}
}

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