Submission #1105025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105025		Nonoze	Parachute rings (IOI12_rings)	C++17	37 / 100	1342 ms	255812 KiB

rings

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

#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)

template<typename T> void read(T& x) { cin >> x;}
template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second);}
template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); }
template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y); }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); }
template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; }

#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define QYES quit("YES")
#define QNO quit("NO")

// #define int long long
#define double long double
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;

int n, cnt;
vector<int> par, sz;
vector<vector<int>> contains;
vector<set<int>> adj;
set<int> critical;

int find(int x) {
	if (x==par[x]) return x;
	return par[x] = find(par[x]);
}

bool same(int a, int b) {
	return find(a)==find(b);
}

void merge(int a, int b) {
	a = find(a), b = find(b);
	if (a==b) return;
	if (sz[a]<sz[b]) swap(a, b);
	par[b] = a;
	sz[a] += sz[b];
	for (int i=1; i<4; i++) {
		contains[a][i] += contains[b][i];
	}
}

vector<bool> visited;

bool dfs(int x, int par=-1) {
	visited[x]=1;
	int cnt=0;
	for (auto u: adj[x]) {
		if (u==par) continue;
		if (cnt==1 || visited[u]) {
			return 0;
		}
		if (!dfs(u, x)) return 0;
		cnt++;
	}
	return 1;
}

bool works(int a, bool real=1, int past=-1) {
	if (real) {
		for (auto u: adj[a]) {
			if (!works(u, 0, a)) return 0;
		}
		return 1;
	}
	if (sz(adj[a])>2) return 0;
	visited.assign(n, 0);
	visited[a]=1;
	// cout << a << ' ' << sz(adj[a]) << ' ' << past << endl;
	// if (a==1499) {
	// 	cout << *adj[a].begin() << ' ' << *next(adj[a].begin()) << endl;
	// 	cout << dfs(*next(adj[a].begin()), a) << ' ' << dfs(*adj[a].begin(), a) << endl;
	// 	visited.assign(n, 0);
	// 	visited[a]=1;
	// }
	if (sz(adj[a])>1) return (dfs(*adj[a].begin(), a) && dfs(*next(adj[a].begin()), a));
	else if (sz(adj[a])) return dfs(*adj[a].begin(), a);
	assert(0);
}

void Init(int N_) {
	n = N_;
	cnt=n;
	par.resize(n), sz.resize(n, 1), contains.resize(n, vector<int>(4, 0));
	iota(all(par), 0);
	adj.resize(n);
	for (int i=0; i<n; i++) critical.insert(i);
}

void Link(int a, int b) {
	if (critical.empty()) return;
	if (a>b) swap(a, b);
	if (same(a, b) || sz(adj[a])>=2 || sz(adj[b])>=2) {
		if (sz(adj[a])>=3 || sz(adj[b])>=3) {
			int cnta=critical.count(a), cntb=critical.count(b);
			critical.clear();
			if (sz(adj[b])<3 && cnta) critical.insert(a);
			else if (sz(adj[a])<3 && cntb) critical.insert(b);
			contains[find(a)][min(sz(adj[a]), 3)]--;
			contains[find(b)][min(sz(adj[b]), 3)]--;
			adj[a].insert(b), adj[b].insert(a);
			contains[find(a)][min(sz(adj[a]), 3)]++;
			contains[find(b)][min(sz(adj[b]), 3)]++;
			return;
		}
		// cout << "OK" << ' ' << same(a, b) << ' ' << sz(adj[a]) << ' ' << sz(adj[b]) << endl;
		// cout << a << ' ' << b << endl;
		// for (auto u: adj[a]) cout << u << ' ';
		// cout << endl;
		// for (auto u: adj[b]) cout << u << ' ';
		// cout << endl;
		// if (sz(critical)<10) for (auto u: critical) cout << u << endl;
		// cout << endl;
		contains[find(a)][min(sz(adj[a]), 3)]--, contains[find(b)][min(sz(adj[b]), 3)]--;
		contains[find(a)][min(sz(adj[a])+1, 3)]++, contains[find(a)][min(sz(adj[b])+1, 3)]++;
		if (sz(critical)==n) {
			critical.clear();
			for (int i=0; i<n; i++) {
				if (i==a || i==b || (find(i)==find(a) && sz(adj[a])<2 && sz(adj[b])<2)) {
					critical.insert(i);
				} else if ((adj[a].count(i) && sz(adj[b])<2) || (adj[b].count(i) && sz(adj[a])<2)) {
					critical.insert(i);
				}
			}
		} else {
			set<int> neww;
			for (auto u: critical) {
				if (u==a || u==b) {
					neww.insert(u);
				} else if (((adj[a].count(u) && sz(adj[b])<2) || (adj[b].count(u) && sz(adj[a])<2))) {// || (adj[a].count(u) && adj[b].count(u)))) {
					neww.insert(u);
				} else if (find(u)==find(a) || find(u)==find(b)) {
					adj[a].insert(b), adj[b].insert(a);
					for (auto x: adj[u]) adj[x].erase(u);
					if (works(u)) neww.insert(u);
					for (auto x: adj[u]) adj[x].insert(u);
					adj[a].erase(b), adj[b].erase(a);
				}
			}
			critical=neww;
		}
		merge(a, b);
		adj[a].insert(b), adj[b].insert(a);
		return;
	}
	merge(a, b);
	contains[find(a)][sz(adj[a])]--;
	contains[find(b)][sz(adj[b])]--;
	adj[a].insert(b), adj[b].insert(a);
	contains[find(a)][sz(adj[a])]++;
	contains[find(b)][sz(adj[b])]++;
}

int CountCritical() {
	return sz(critical);
}

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