Submission #760664

#	Time	Username	Problem	Language	Result	Execution time	Memory
760664		ymm	Parachute rings (IOI12_rings)	C++17	100 / 100	1110 ms	130160 KiB

rings

#include <bits/stdc++.h>
#define Loop(x,l,r)  for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 1<<20;
vector<int> A[N];
int n;

struct graph {
	int deg[N];
	int rem;
	int par[N];
	bool has3;
	int sz[N];
	int szc;

	void init() {
		fill(par, par+N, -1);
		fill(sz, sz+N, 1);
		szc = -1;
		rem = -1;
	}
	int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
	void unite(int v, int u) {
		if (v == rem || u == rem)
			return;
		deg[v]++;
		deg[u]++;
		if (deg[v] >= 3 || deg[u] >= 3)
			has3 = 1;
		v = rt(v);
		u = rt(u);
		if (v == u) {
			szc = szc == -1? sz[v]: -2;
			return;
		}
		if (sz[v] < sz[u])
			swap(v, u);
		par[u] = v;
		sz[v] += sz[u];
	}
};

void make_by_rem(graph &G, int rem) {
	G.init();
	G.rem = rem;
	Loop (v,0,n) {
		for (int u : A[v]) {
			if (v > u)
				continue;
			G.unite(v, u);
		}
	}
}

graph G, G3[4];

int v3 = -1;

void Init(int N_) {
	n = N_;
	G.init();
}

void Link(int v, int u) {
	A[v].push_back(u);
	A[u].push_back(v);

	if (v3 != -1) {
		for (auto &G : G3)
			G.unite(v, u);
	} else {
		G.unite(v, u);
	}

	for (int x : {v, u}) {
		if (v3 == -1 && A[x].size() == 3) {
			v3 = x;
			make_by_rem(G3[0], x);
			Loop (i,0,3)
				make_by_rem(G3[i+1], A[x][i]);
		}
	}
}

int CountCritical() {
	if (v3 != -1) {
		int ans = 0;
		for (auto &G : G3)
			ans += G.szc == -1 && !G.has3;
		return ans;
	} else {
		switch (G.szc) {
		case -2: return 0;
		case -1: return n;
		default: return G.szc;
		}
	}
}

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