Submission #56594

#	Time	Username	Problem	Language	Result	Execution time	Memory
56594		kingpig9	Parachute rings (IOI12_rings)	C++11	52 / 100	4024 ms	156556 KiB

rings

#include <bits/stdc++.h>
//#include "rings.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e6 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N;
int status;
vector<int> adj[MAXN];
unordered_set<int> verts[5];	//verts[min(degree, 4)]

#define end enddd
int ntest;

struct union_find {
	int exc;	//vertex to be exluced
	bool ok;	//is this answer good?
	int ncyc, szcyc;	//# of cycles, size of one of the cycles if there is any.
	int par[MAXN];
	int start[MAXN], end[MAXN];
	int nedge[MAXN];	//lol I forgot the case of CYCLES!! :(
	int sz[MAXN];

	void reset (int e) {
		exc = e;
		ok = true;
		ncyc = 0;
		for (int i = 0; i < N; i++) {
			par[i] = i;
			start[i] = i;
			end[i] = i;
			nedge[i] = 0;
			sz[i] = 1;
		}
	}

	int find (int x) {
		return x == par[x] ? x : par[x] = find(par[x]);
	}

	void merge (int a, int b) {
		if ((!ok && status > 2) || a == exc || b == exc) {
			return;
		}

		int fa = find(a), fb = find(b);
		if (fa == fb) {
			ncyc -= (sz[fa] == nedge[fa]);
			nedge[fa]++;
			ncyc += (sz[fa] == nedge[fa]);
			if (sz[fa] == nedge[fa]) {
				szcyc = sz[fa];
			}
			ok = false;
			return;
		}

		if (a != end[fa]) {
			swap(start[fa], end[fa]);
		}
		if (b != start[fb]) {
			swap(start[fb], end[fb]);
		}

		if (a != end[fa] || b != start[fb]) {
			ok = false;
			return;
		}

		par[fb] = fa;
		end[fa] = end[fb];

		ncyc -= (sz[fa] == nedge[fa]);
		ncyc -= (sz[fb] == nedge[fb]);
		nedge[fa] = nedge[fa] + nedge[fb] + 1;
		sz[fa] += sz[fb];
		ncyc += (sz[fa] == nedge[fa]);
		if (sz[fa] == nedge[fa]) {
			assert(status >= 3);
			szcyc = sz[fa];
		}
	}
} uf[4];

void Init (int nnnn) {
	N = nnnn;

	//ok now do something else
	for (int i = 0; i < N; i++) {
		verts[0].insert(i);
	}

	ntest = 1;
	uf[0].reset(-1);
	status = 0;
}

void settest (vector<int> v) {
	ntest = v.size();

	for (int i = 0; i < ntest; i++) {
		uf[i].reset(v[i]);
		for (int x = 0; x < N; x++) {
			for (int y : adj[x]) {
				if (x < y) {
					uf[i].merge(x, y);
				}
			}
		}
	}
}

void Link (int a, int b) {
	if (status == -1) {
		return;
	}

	for (int v : {a, b}) {
		assert(verts[min(4, (int) adj[v].size())].erase(v));
	}
	adj[a].push_back(b);
	adj[b].push_back(a);
	for (int v : {a, b}) {
		verts[min(4, (int) adj[v].size())].insert(v);
	}

	//recalc status
	status = 4;
	while (verts[status].empty()) {
		status--;
	}

	for (int i = 0; i < ntest; i++) {
		uf[i].merge(a, b);	//hmm "merge" is pretty bad for this case...
	}

	if (status == 3) {
		if (ntest == 1) {
			int v = *verts[3].begin();
			settest(vector<int> {v, adj[v][0], adj[v][1], adj[v][2]});
		}
	} else if (status == 4) {
		if (verts[4].size() > 1) {
			status = -1;
			return;
		}
		//otherwise, leave it to this one
		if (ntest == 4) {
			settest(vector<int> {*verts[4].begin()});
		}
	}
}

int CountCritical() {
	if (status == -1) {
		return 0;
	}

	int ans = 0;
	if (status <= 2) {
		if (uf[0].ncyc == 0) {
			ans = N;
		} else if (uf[0].ncyc == 1) {
			ans = uf[0].szcyc;
		} else {
			ans = 0;
		}
	} else {
		for (int i = 0; i < ntest; i++) {
			ans += uf[i].ok;
		}
	}

	if (ans == 0) {
		status = -1;
	}
	return ans;
}

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