Submission #594944

#	Time	Username	Problem	Language	Result	Execution time	Memory
594944		8e7	Parachute rings (IOI12_rings)	C++17	17 / 100	1524 ms	134916 KiB

rings

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second

struct DSU{
	int par[maxn], siz[maxn];
	void init(int n){
		for (int i = 1;i <= n;i++) par[i] = i, siz[i] = 1;
	}
	int find(int a){
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	bool Union(int a, int b){
		a = find(a), b = find(b);
		if (a == b) return 0;
		if (siz[a] < siz[b]) swap(a, b);
		par[b] = a;
		siz[a] += siz[b];
		return 1;
	}
};
struct graph{ //maintaining a graph of nodes with deg <= 2
	DSU d;
	int deg[maxn];
	int cycle = 0, ignore = -1, count = 0;
	bool good = 1;
	int maxdeg = 0;
	void addedge(int u, int v){
		if (u == ignore || v == ignore) return;
		deg[u]++, deg[v]++;
		maxdeg = max(maxdeg, max(deg[u], deg[v]));
		if (maxdeg > 2) {
			good = 0;
			return;
		}
		if (!d.Union(u, v)) {
			cycle++;	
			if (cycle > 1) good = 0;
			else count = d.siz[d.find(u)];
		}	
	}	
} g;
vector<int> adj[maxn];
vector<pii> ed;
int N;
void Init(int N_) {
	N = N_;
	g.d.init(N);
}
graph cand[4];
int idx = 0;
void Link(int A, int B) {
	adj[A].push_back(B);
	adj[B].push_back(A);
	ed.push_back({A, B});
	if (g.maxdeg < 3) {
		g.addedge(A, B);
		if (g.maxdeg >= 3) {
			if (g.deg[B] >= 3) swap(A, B);
			adj[A].push_back(A);
			for (int i:adj[A]) {
				graph &tmp = cand[idx++];
				tmp.d.init(N);
				tmp.ignore = i;
				for (auto p:ed) tmp.addedge(p.ff, p.ss);
			}
			adj[A].pop_back();
		}
	} else {
		for (auto &t:cand){
			t.addedge(A, B);	
		}
	}
}

int CountCritical() {
	if (g.good) {
		if (g.cycle == 1) return g.count;
		else return N;
	} else {
		int ret = 0;
		for (int t = 0;t < idx;t++) {
			if (cand[t].good && cand[t].cycle == 0) ret++;
		}
		return ret;
	}
}

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