Submission #1024154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024154		socpite	Parachute rings (IOI12_rings)	C++17	100 / 100	704 ms	135080 KiB

rings

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

int N;

int current_state, ans; // 0: all chain, 1: ring, 2: 1 non-ring 3: return 0

const int maxn = 1e6+5;

int up[maxn], L[maxn], R[maxn];

vector<pair<int, int>> E;
vector<int> g[maxn];

int Find(int x){
	return up[x] < 0 ? x : up[x] = Find(up[x]);
}

struct dsu{
	int nd, state;
	vector<int> up, L, R;
	int Find(int x){
		return up[x] < 0 ? x : up[x] = Find(up[x]);
	}
	void Union(int a, int b){
		// cout << "UNION " << a << " " << b << endl;
		if(a == nd || b == nd)return;
		if(!state)return;
		int ra = Find(a), rb = Find(b);
		if(ra == rb){
			state = 0;
			return;
		}
		if(a != L[ra])swap(L[ra], R[ra]);
		if(b != L[rb])swap(L[rb], R[rb]);
		if(a != L[ra] || b != L[rb]){
			state = 0;
			return;
		}
		up[rb] = ra;
		L[ra] = R[rb];
	}
	dsu(int _nd): nd(_nd){
		up.assign(N, -1);
		L.resize(N);
		R.resize(N);
		for(int i = 0; i < N; i++)L[i] = R[i] = i;
		state = 1;
		for(auto v: E)Union(v.first, v.second);
	}
};
vector<dsu> candidates;

void init_cen(int x){
	current_state = 2;
	candidates.push_back(dsu(x));
	for(auto v: g[x])candidates.push_back(dsu(v));
}

void Union(int a, int b){ // only happens while in state 0 or 1
	int ra = Find(a), rb = Find(b);
	if(ra == rb){
		if(current_state == 1){
			current_state = 3;
			return;
		}
		L[ra] = R[ra] = -1;
		current_state = 1;
		ans = -up[ra];
	}
	else {
		if(a != L[ra])swap(L[ra], R[ra]);
		if(b != L[rb])swap(L[rb], R[rb]);
		up[ra] += up[rb];
		up[rb] = ra;
		L[ra] = R[rb];
	}
}

void Init(int N_) {
	current_state = 0;
	N = N_;
	ans = N;
	candidates.clear();
	E.clear();
	for(int i = 0; i < N; i++){
		g[i].clear();
		up[i] = -1;
		L[i] = R[i] = i;
	}
}

void Link(int A, int B) {
	E.push_back({A, B});
	g[A].push_back(B);
	g[B].push_back(A);
	if(current_state <= 1){
		if(g[A].size() >= 3)init_cen(A);
		else if(g[B].size() >= 3)init_cen(B);
		else Union(A, B);
	}
	else {
		for(auto &v: candidates)v.Union(A, B);
	}
}

int CountCritical() {
	if(current_state <= 1)return ans;
	else {
		int sum = 0;
		for(auto &v: candidates)sum += v.state;
		return sum;
	}

}

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