Submission #761131

#	Time	Username	Problem	Language	Result	Execution time	Memory
761131		SanguineChameleon	Parachute rings (IOI12_rings)	C++17	0 / 100	271 ms	60092 KiB

rings

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 20;
vector<pair<int, int>> edges;
int deg[4][maxn];
int L[4][maxn];
int R[4][maxn];
int cand[4];
bool good[4];
int n;

void Init(int _n) {
	n = _n;
	for (int k = 0; k < 4; k++) {
		cand[k] = -1;
	}
}

void update(int k, int u, int v) {
	if (!good[k]) {
		return;
	}
	if (u == cand[k] || v == cand[k]) {
		return;
	}
	if (deg[k][u] == 2 || deg[k][v] == 2) {
		good[k] = false;
		return;
	}
	deg[k][u]++;
	deg[k][v]++;
	int lu = L[k][u];
	int ru = R[k][u];
	int lv = L[k][v];
	int rv = R[k][v];
	if (lu == lv) {
		good[k] = false;
		return;
	}
	if (lu == u) {
		swap(lu, ru);
		L[k][lu] = lu;
		L[k][ru] = lu;
		R[k][lu] = ru;
		R[k][ru] = ru;
	}
	if (rv == v) {
		swap(lv, rv);
		L[k][lv] = lv;
		L[k][rv] = lv;
		R[k][lv] = rv;
		R[k][rv] = rv;
	}
	L[k][lu] = lu;
	R[k][lu] = rv;
	L[k][rv] = lu;
	R[k][rv] = rv;
}

void Link(int u, int v) {
	if (cand[0] == -1) {
		edges.emplace_back(u, v);
		deg[0][u]++;
		deg[0][v]++;
		if (deg[0][v] == 3) {
			swap(u, v);
		}
		if (deg[0][u] == 3) {
			cand[0] = u;
			int cnt = 0;
			for (auto e: edges) {
				if (e.first == u) {
					cand[++cnt] = e.second;
				}
				else if (e.second == u) {
					cand[++cnt] = e.first;
				}
			}
			for (int k = 0; k < 4; k++) {
				good[k] = true;
				for (int i = 0; i < n; i++) {
					deg[k][i] = 0;
					L[k][i] = i;
					R[k][i] = i;
				}
			}
			for (auto e: edges) {
				for (int k = 0; k < 4; k++) {
					update(k, e.first, e.second);
				}
			}
			edges.clear();
		}
	}
	else {
		for (int k = 0; k < 4; k++) {
			update(k, u, v);
		}
	}
}

int CountCritical() {
	if (cand[0] == -1) {
		return n;
	}
	else {
		return good[0] + good[1] + good[2] + good[3];
	}
}

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