Submission #64055

#	Time	Username	Problem	Language	Result	Execution time	Memory
64055		chpipis	Parachute rings (IOI12_rings)	C++11	37 / 100	3436 ms	76156 KiB

rings

#ifndef EVAL
#include "grader.h"
#endif
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int MAXN = 1e6 + 5;

vector<int> gr[MAXN];
int deg[MAXN], neig3[MAXN];
int p[MAXN], sz[MAXN];
int n, numcc, total, curcycle;
int great_node;
map<int, int> cnt;
set<int> three;
bool visit[MAXN];

void Init(int _n) {
	n = _n;
	for (int i = 0; i < n; i++) {
		deg[i] = 0;
		p[i] = -1;
		sz[i] = 1;
		gr[i].clear();
	}
	numcc = n;
	total = n;
	cnt.clear();
	cnt[0] = n;
}

int fin(int x) {
	return (p[x] == -1 ? x : p[x] = fin(p[x]));
}

inline void chval(int x, int add) {
	if (deg[x] == 3)
		three.erase(x);
	cnt[deg[x]]--;
	if (cnt[deg[x]] == 0)
		cnt.erase(deg[x]);
	deg[x] += add;
	cnt[deg[x]]++;
	if (deg[x] == 3)
		three.insert(x);
}

void dfs(int u) {
	visit[u] = true;
	for (auto v : gr[u]) {
		if (visit[v]) continue;
		dfs(v);
	}
}

bool check(int w) {
	for (auto v : gr[w])
		chval(v, -1);
	memset(visit, false, sizeof visit);
	visit[w] = true;
	int comps = cnt[0] + cnt[1] / 2;
	int want = 0;
	for (int u = 0; u < n; u++) {
		if (!visit[u]) {
			want++;
			dfs(u);
		}
	}
	for (auto v : gr[w])
		chval(v, +1);
	return want == comps;
}

void Link(int a, int b) {
	if (deg[a] == 3) {
		for (auto v : gr[a])
			neig3[v]--;
	}
	if (deg[b] == 3) {
		for (auto v : gr[b])
			neig3[v]--;
	}
	chval(a, +1);
	chval(b, +1);
	gr[a].pb(b);
	gr[b].pb(a);
	if (deg[a] == 3) {
		for (auto v : gr[a])
			neig3[v]++;
	}
	if (deg[b] == 3) {
		for (auto v : gr[b])
			neig3[v]++;
	}
	if (deg[a] > 3) {
		great_node = a;
	} else if (deg[b] > 3) {
		great_node = b;
	}
	int ra = fin(a), rb = fin(b);
	if (ra != rb) {
		numcc--;
		if (sz[ra] > sz[rb]) {
			p[rb] = ra;
			sz[ra] += sz[rb];
		} else {
			p[ra] = rb;
			sz[rb] += sz[ra];
		}
	} else {
		curcycle = sz[ra];
		if (!three.empty() && fin(*three.begin()) != ra) {
			total = 0;
			return;
		}
	}
	int big = 0;
	for (auto it = cnt.rbegin(); it != cnt.rend(); it++) {
		if (it->first <= 3) break;
		big += it->second;
		if (big > 1) break;
	}
	if (big == 0 && cnt[3] == 0) {
		// everything is either a chain or a cycle
		int comps = cnt[0] + cnt[1] / 2;
		if (comps == numcc) {
			// every component is a chain
			total = n;
		} else if (comps == numcc - 1) {
			total = curcycle;
		} else {
			total = 0;
		}
	} else if (big > 1 || cnt[3] > 4) {
		total = 0;
	} else if (big == 1) {
		if (neig3[great_node] != (int)three.size()) {
			total = 0;
		} else {
			bool found = (great_node == a || great_node == b);
			for (auto v : gr[a])
				if (v == great_node)
					found = true;
			for (auto v : gr[b])
				if (v == great_node)
					found = true;
			if (found) {
				if (check(great_node)) {
					total = 1;
				} else {
					total = 0;
				}
			}
		}
	} else {
		// now big = 0 and cnt[3] > 0
		const int c = (int)three.size();
		set<int> proc;
		for (auto u : three) {
			proc.insert(u);
			for (auto v : gr[u])
				proc.insert(v);
		}
		bool found = false;
		for (auto it : proc) {
			if (it == a || it == b)
				found = true;
		}
		if (!found) return;
		total = 0;
		for (auto u : proc) {
			if (deg[u] == 3 && neig3[u] == c - 1) {
				if (check(u))
					total++;
			} else if (deg[u] < 3 && neig3[u] == c) {
				if (check(u))
					total++;
			}
		}
	}
}

int CountCritical() {
	return total;
}

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