Submission #382407

#	Time	Username	Problem	Language	Result	Execution time	Memory
382407		aarr	Parachute rings (IOI12_rings)	C++14	0 / 100	4067 ms	90408 KiB

rings

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

int n, ans;
const int N = 1000 * 1000 + 5;

set <pair <int, int> > s;
vector <int> adj[N];
int deg[N];
bool g2 = false;
bool b[N];
vector <int> vec;
bool mark[N];

void Init(int N_) {
	n = N_;
	
  

}

inline int f(int v) {
	int res = 0;
	fill(mark, mark + n + 1, false);
	mark[v] = true;
	for (auto u : adj[v]) {
		deg[u]--;
	}
	for (int i = 0; i < n; i++) {
		if (i == v) {
			continue;
		}
		if (deg[i] > 2) {
			for (auto u : adj[v]) {
				deg[u]++;
			}
			return -1;
		}	
		if (deg[i] < 2) {
			int u = i;
			do {
				bool d = false;
			
				mark[u] = true;
				for (auto w : adj[u]) {
					if (!mark[w]) {
						u = w;
						d = true;
						break;
					}
				}
				if (!d) {
					break;
				}
				
			} while(u != i);
		}
	}
	for (int i = 0; i < n; i++) {
		if (!mark[i]) {
			res++;
		}
	}
	for (auto u : adj[v]) {
		deg[u]++;
	}
	return res;
}

inline void check(int v) {
	if (b[v]) {
		return;
	}
	if (f(v) == 0) {
	//	cout << "72 " << v << endl;
		b[v] = true;
		ans++;
		vec.push_back(v);
	}
}

void Link(int A, int B) {
	s.erase({-deg[A], A});
	s.erase({-deg[B], B});
	deg[A]++;
	deg[B]++;
	if (deg[A] > 2 || deg[B] > 2) {
		g2 = true;
	}
	adj[A].push_back(B);
	adj[B].push_back(A);
	s.insert({-deg[A], A});
	s.insert({-deg[B], B});
}

int CountCritical() {
	ans = 0;
	vec.clear();
	if (g2) {
		set <pair <int, int> > :: iterator it = s.begin();
		for (int i = 0; i < 4; i++) {
			if (it == s.end()) {
				break;
			}
			int v = (*it).second;
			check(v);
			if (deg[v] < 4) {
				for (auto u : adj[v]) {
					check(u);
				}
			}
		}
		for (auto x : vec) {
			b[x] = false;
		}
		return ans;
	}
	else {
		int x = f(n + 1);
		if (x == -1) {
			return 0;
		}
		if (x == 0) {
			return n;
		}
		return x;
	}
}

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