Submission #1012044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012044		AmirAli_H1	Parachute rings (IOI12_rings)	C++17	100 / 100	866 ms	138920 KiB

rings

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		X						real()
#define		Y						imag()
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 4;

int n;
vector<int> adj[maxn];
vector<pii> E; pii delta;
int p[4][maxn], sz[4][maxn];
int numx[4], valx[4], R, Rx; pii val[4][maxn];

int get(int ind, int u) {
	return p[ind][u] == u ? u : p[ind][u] = get(ind, p[ind][u]);
}

void merge(int ind, int ux, int vx) {
	int u = get(ind, ux), v = get(ind, vx);
	if (sz[ind][u] > sz[ind][v]) {
		swap(ux, vx); swap(u, v);
	}
	
	if (u == v) {
		numx[ind]++; Rx = sz[ind][v];
		return ;
	}
	int u1 = val[ind][u].F, u2 = val[ind][u].S;
	int v1 = val[ind][v].F, v2 = val[ind][v].S;
	for (int T1 = 0; T1 < 2; T1++) {
		for (int T2 = 0; T2 < 2; T2++) {
			if (u2 == ux && v2 == vx) {
				p[ind][u] = v; sz[ind][v] += sz[ind][u];
				val[ind][v] = Mp(u1, v1);
				return ;
			}
			swap(v1, v2);
		}
		swap(u1, u2);
	}
	numx[ind]++; Rx = sz[ind][v];
	return ;
}

void build(int ind, int x) {
	numx[ind] = 0; valx[ind] = x;
	for (int i = 0; i < n; i++) {
		p[ind][i] = i; sz[ind][i] = 1;
		val[ind][i] = Mp(i, i);
	}
	for (auto f : E) {
		int u = f.F, v = f.S;
		if (u == valx[ind] || v == valx[ind]) continue;
		merge(ind, u, v);
	}
}

void rebuild3() {
	int v = delta.S; R = 0;
	build(R, v); R++;
	for (int u : adj[v]) {
		build(R, u); R++;
	}
}

void rebuild4() {
	int v = delta.S; R = 0;
	build(R, v); R++;
}

void Init(int N) {
	n = N; delta = Mp(0, 0);
	R = 1; build(0, -1);
}

void Link(int u, int v) {
	E.pb(Mp(u, v));
	adj[u].pb(v); adj[v].pb(u);
	for (int i = 0; i < R; i++) {
		if (u == valx[i] || v == valx[i]) continue;
		merge(i, u, v);
	}
	for (int x : {u, v}) {
		if (len(adj[x]) > delta.F) {
			delta = Mp(len(adj[x]), x);
			if (delta.F == 3) rebuild3();
			else if (delta.F == 4) rebuild4();
		}
	}
}

int CountCritical() {
	if (delta.F <= 1) return n;
	else if (delta.F == 2) {
		if (numx[0] == 0) return n;
		else if (numx[0] == 1) return Rx;
		else return 0;
	}
	else {
		int ans = 0;
		for (int i = 0; i < R; i++) {
			if (numx[i] == 0) ans++;
		}
		return ans;
	}
}

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