Submission #1105003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105003		Nonoze	Parachute rings (IOI12_rings)	C++17	37 / 100	1238 ms	258196 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<pair<int, 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];
	}
}

bool works(int a) {
	a=find(a);
	if (sz[a]<=2) return 1;
	if (contains[a][1]==2 && contains[a][3]==0) return 1;
	return 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, 1});
}

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, 1})||critical.count({a, 0}), cntb=critical.count({b, 1})||critical.count({b, 0});
			critical.clear();
			if (sz(adj[b])<3 && cnta) critical.insert({a, 1});
			else if (sz(adj[a])<3 && cntb) critical.insert({b, 1});
			return;
		}
		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, 1});
				} else if ((adj[a].count(i) && sz(adj[b])<2) || (adj[b].count(i) && sz(adj[a])<2)) {
					critical.insert({i, 0});
				}
			}
		} else {
			set<pair<int, int>> neww;
			for (auto u: critical) {
				if (u.fi==a || u.fi==b) {
					neww.insert({u.fi, 1});
				} else if (((adj[a].count(u.fi) && sz(adj[b])<2) || (adj[b].count(u.fi) && sz(adj[a])<2))) {
					neww.insert({u.fi, 0});
				}
			}
			critical=neww;
		}
		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(a)][sz(adj[b])]++;
		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