Submission #105091

#	Time	Username	Problem	Language	Result	Execution time	Memory
105091		eriksuenderhauf	Parachute rings (IOI12_rings)	C++11	100 / 100	1781 ms	110044 KiB

rings

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#include "grader.h"
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
using namespace std;
const int MAXN = 1e6 + 5;
int par[MAXN], deg[MAXN], cycle = 0, cnt[MAXN], n = 0;
int mrk[MAXN];
vi cand, adj[MAXN];

struct DSU {
	int par[MAXN], deg[MAXN], root = 0;
	bool valid = true;
	int qry(int x) {
		if (!valid) return 0;
		return x == par[x] ? x : par[x] = qry(par[x]);
	}

	void join(int u, int v) {
		if (!valid) return;
		u = qry(u), v = qry(v);
		par[u] = v;
	}

	void init(int n) {
		for (int i = 0; i < n; i++)
			par[i] = i;
	}
} e, f;

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

void join(int u, int v) {
	u = qry(u), v = qry(v);
	par[u] = v;
}

void Init(int N) {
	n = N;
	for (int i = 0; i < N; i++) {
		par[i] = i;
		cand.pb(i);
		mrk[i] = 1;
	}
}

void do3(int b) {
	vi tmp;
	for (int v: adj[b])
		if (mrk[v])
			tmp.pb(v);
	if (mrk[b])
		tmp.pb(b);
	for (int v: cand)
		mrk[v] = 0;
	for (int v: tmp)
		mrk[v] = 1;
	cand = tmp;
}

int par2[MAXN];
bool fin = false;
vii edg;

void dfs(int u, int p) {
	par2[u] = p;
	for (int v: adj[u])
		if (v != p)
			dfs(v, u);
}

void addE(int u, int v) {
	if (u == e.root || v == e.root || e.valid == false) return;
	e.deg[u]++, e.deg[v]++;
	if (e.qry(u) == e.qry(v) || e.deg[u] > 2 || e.deg[v] > 2)
		e.valid = false;
	e.join(u, v);
}
void addF(int u, int v) {
	if (u == f.root || v == f.root || f.valid == false) return;
	f.deg[u]++, f.deg[v]++;
	if (f.qry(u) == f.qry(v) || f.deg[u] > 2 || f.deg[v] > 2)
		f.valid = false;
	f.join(u, v);
}

void Link(int a, int b) {
	if (cand.empty()) return;
	if (fin) {
		addE(a, b);
		addF(a, b);
		return;
	}
	edg.pb({a, b});
	int delta = 0;
	if (qry(a) == qry(b) && cycle == 0) {
		dfs(a, -1);
		vi tmp = {a};
		int u = b;
		while (u != a) {
			tmp.pb(u);
			u = par2[u];
		}
		vi nx;
		for (int i: tmp)
			if (mrk[i] == 1) {
				nx.pb(i);
				mrk[i] = 2;
			}
		for (int i: cand)
			mrk[i]--;
		cand = nx;
	}
	adj[a].pb(b);
	adj[b].pb(a);
	if (qry(a) == qry(b)) {
		delta++;
		cycle++;
	}
	cnt[deg[a]]--;
	cnt[deg[b]]--;
	deg[a]++, deg[b]++;
	cnt[deg[a]]++;
	cnt[deg[b]]++;
	if (cnt[4] > 1) {
		cand = {};
		return;
	}
	if (deg[a] > deg[b])
		swap(a, b);
	if (deg[b] == 3) do3(b);
	if (deg[a] == 3) do3(a);
	if (deg[b] == 4) {
		if (!mrk[b]) {
			cand = {};
			return;
		}
		memset(mrk, 0, sizeof mrk);
		mrk[b] = 1;
		cand = {b};
	}
	join(a, b);
	if (cand.empty()) return;
	if (cycle > 1 && delta > 0) {
		if (qry(a) != qry(cand[0])) {
			cand = {};
			return;
		}
		if (mrk[a] && mrk[b]) {
			cand = {a, b};
			memset(mrk, 0, sizeof mrk);
			mrk[a] = 1, mrk[b] = 1;
		} else if (mrk[a] || mrk[b]) {
			if (mrk[a]) {
				memset(mrk, 0, sizeof mrk);
				mrk[a] = 1;
				cand = {a};
			} else {
				memset(mrk, 0, sizeof mrk);
				mrk[b] = 1;
				cand = {b};
			}
		}
		fin = true;
		if (cand.size() == 1) {
			f.valid = false;
			e.init(n);
			e.root = cand[0];
			for (int i = 0; i < edg.size(); i++) {
				int u, v;
				tie(u, v) = edg[i];
				if (u == cand[0] || v == cand[0]) continue;
				e.deg[u]++, e.deg[v]++;
				if (e.qry(u) == e.qry(v) || e.deg[u] > 2 || e.deg[v] > 2) {
					cand = {};
					return;
				}
				e.join(u, v);
			}
		} else {
			e.init(n);
			e.root = cand[0];
			for (int i = 0; e.valid && i < edg.size(); i++) {
				int u, v;
				tie(u, v) = edg[i];
				if (u == cand[0] || v == cand[0]) continue;
				e.deg[u]++, e.deg[v]++;
				if (e.qry(u) == e.qry(v) || e.deg[u] > 2 || e.deg[v] > 2)
					e.valid = false;
				e.join(u, v);
			}
			f.init(n);
			f.root = cand[1];
			for (int i = 0; f.valid && i < edg.size(); i++) {
				int u, v;
				tie(u, v) = edg[i];
				if (u == cand[1] || v == cand[1]) continue;
				f.deg[u]++, f.deg[v]++;
				if (f.qry(u) == f.qry(v) || f.deg[u] > 2 || f.deg[v] > 2)
					f.valid = false;
				f.join(u, v);
			}
		}
	}
}

int CountCritical() {
	int ret = 0;
	if (fin) {
		ret += (e.valid ? 1 : 0);
		ret += (f.valid ? 1 : 0);
		return ret;
	}
	return cand.size();
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:174:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < edg.size(); i++) {
                    ~~^~~~~~~~~~~~
rings.cpp:188:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; e.valid && i < edg.size(); i++) {
                               ~~^~~~~~~~~~~~
rings.cpp:199:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; f.valid && i < edg.size(); i++) {
                               ~~^~~~~~~~~~~~

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