Submission #1196951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196951		alterio	Parachute rings (IOI12_rings)	C++20	0 / 100	4097 ms	255884 KiB

rings

#include <bits/stdc++.h>

using namespace std;

const int mxn = 1e6 + 10;

vector<int> g[mxn], deg(mxn), ldr(mxn), rnk(mxn), cycle(mxn), LDR(mxn), RNK(mxn);
set<int> S[mxn], act, hasCycle;
set<pair<int, int>> edg;
multiset<int> vals;
int N, mx, cnt, cycles, foundX = -1, foundY = -1;

int FIND(int x) {
	if (x == LDR[x]) return x;
	return LDR[x] = FIND(LDR[x]);
}

void UNION(int x, int y) {
	x = FIND(x), y = FIND(y);
	if (x == y) return;
	if (RNK[y] > RNK[x]) swap(x, y);
	RNK[x] += RNK[y];
	LDR[y] = x;
}

int Find(int x) {
	if (x == ldr[x]) return x;
	return ldr[x] = Find(ldr[x]);
}

void Union(int x, int y) {
	x = Find(x), y = Find(y);
	if (x == y) cycles++, cycle[x]++, hasCycle.insert(x);
	else {
		if (rnk[y] > rnk[x]) swap(x, y);
		ldr[y] = x;
		act.erase(y);
		if (hasCycle.count(y)) hasCycle.erase(y);
		rnk[x] += rnk[y];
		cycle[x] += cycle[y];
		if (cycle[x]) hasCycle.insert(x);
	}
}

void Init(int N_) {
	N = N_;
	for (int i = 0; i < N; i++) S[0].insert(i), ldr[i] = i, LDR[i] = i, RNK[i] = 1, rnk[i] = 1, act.insert(i), vals.insert(0);
}

void Link(int A, int B) {
	Union(A, B);
	if (foundX != -1 && A != foundX && A != foundY && B != foundX && B != foundY) UNION(A, B);
	S[deg[A]].erase(A);
	S[deg[B]].erase(B);
	vals.erase(vals.find(deg[A]));
	vals.erase(vals.find(deg[B]));
	deg[A]++, deg[B]++;
	if (deg[A] == 3) cnt++;
	if (deg[B] == 3) cnt++;
	vals.insert(deg[A]);
	vals.insert(deg[B]);
	S[deg[A]].insert(A);
	S[deg[B]].insert(B);
	mx = max({mx, deg[A], deg[B]});
	g[A].push_back(B);
	g[B].push_back(A);
	edg.insert({A, B});
	edg.insert({B, A});
}

int CountCritical() { 
	if (mx < 3) {
		if (cycles <= 1) return N;
		return 0;
	}
	if (cnt > 2) return 0;
	if (cnt == 1 && cycles == 0) return 1 + deg[*S[mx].begin()];
	if (cnt == 1) {
		int node = *S[mx].begin();
		for (auto x : hasCycle) {
			if (Find(x) != Find(node)) return 0;
		}
		if (hasCycle.size() == 1) return 3;
		return 1;
	}
	auto it = vals.rbegin();
	--it;
	if (*it > 3) return 0;
	int nodeOne = *S[mx].begin(), nodeTwo = *S[*it].rbegin();
	for (auto x : hasCycle) {
		if (Find(x) != Find(nodeOne)) return 0;
	}
	if (foundX == -1) {
		foundX = nodeOne, foundY = nodeTwo;
		for (auto x : edg) {
			if (x.first != foundX && x.first != foundY && x.second != foundX && x.second != foundY) {
				UNION(x.first, x.second);
			}
		}
	}
	bool connection = edg.count({nodeOne, nodeTwo});
	if (deg[nodeOne] > 3) {
		if (!connection) return 0;
		for (auto el : g[nodeTwo]) {
			if (el == nodeOne) continue;
			for (auto EL : g[nodeTwo]) {
				if (el == nodeOne) continue;
				if (el == EL) continue;
				if (FIND(el) == FIND(EL)) return 0;
			}
		}
		return 1;
	}
	vector<int> nodes;
	for (auto x : g[nodeOne]) {
		for (auto y : g[nodeTwo]) {
			if (x == y) connection = 1, nodes.push_back(x);
		}
	}
	if (!connection) return 0;
	int ans = 0;
	if (edg.count({nodeOne, nodeTwo})) {
		bool flag = 1;
		for (auto x : g[nodeOne]) {
			if (x == nodeTwo) continue;
			for (auto y : g[nodeOne]) {
				if (y == nodeTwo) continue;
				if (x == y) continue;
				if (FIND(x) == FIND(y)) {
					flag = 0;
				}
			}
		}
		ans += flag;
		flag = 1;
		for (auto x : g[nodeTwo]) {
			if (x == nodeOne) continue;
			for (auto y : g[nodeTwo]) {
				if (y == nodeOne) continue;
				if (x == y) continue;
				if (FIND(x) == FIND(y)) {
					flag = 0;
				}
			}
		}
		ans += flag;
	}
	for (auto x : nodes) {
		bool flag = 1;
		vector<int> rest;
		for (auto el : g[nodeOne]) {
			if (el != x) rest.push_back(el);
		}
		for (auto el : rest) {
			for (auto EL : rest) {
				if (el == EL) continue;
				if (FIND(el) == FIND(EL)) flag = 0;
			}
		}
		if (!edg.count({nodeOne, nodeTwo}) && nodes.size() == 1) rest.clear();
		for (auto el : g[nodeTwo]) {
			if (el != x) rest.push_back(el);
		}
		for (auto el : rest) {
			for (auto EL : rest) {
				if (el == EL) continue;
				if (FIND(el) == FIND(EL)) flag = 0;
			}
		}
		ans += flag;
	}
	return ans;	
}

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