oj.uz

Submission #105067

# Submission time Handle Problem Language Result Execution time Memory
105067 2019-04-10T12:46:16 Z eriksuenderhauf Parachute rings (IOI12_rings) C++11
0 / 100
 833 ms 67992 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#include "grader.h"
#define vi vector<int>
#define pb push_back
using namespace std;
const int MAXN = 1e6 + 5;
int par[MAXN], deg[MAXN], cycle = 0, cnt[MAXN], n = 0;
int mrk[MAXN];
vi cand, adj[MAXN];

int qry(int x) {
	return x == par[x] ? x : par[x] = qry(par[x]);
}

void join(int u, int v) {
	u = qry(u), v = qry(v);
	par[u] = v;
}

void Init(int N) {
	n = N;
	for (int i = 0; i < N; i++) {
		par[i] = i;
		cand.pb(i);
		mrk[i] = 1;
	}
}

void do3(int b) {
	vi tmp;
	for (int v: adj[b])
		if (mrk[v])
			tmp.pb(v);
	if (mrk[b])
		tmp.pb(b);
	for (int v: cand)
		mrk[v] = 0;
	for (int v: tmp)
		mrk[v] = 1;
	cand = tmp;
}

int low[MAXN], disc[MAXN], vis[MAXN];
int t = 0, onStack[MAXN];
stack<int> st;

void tarjan(int u, int p) {
	vis[u] = 1, onStack[u] = 1;
	disc[u] = low[u] = ++t;
	st.push(u);
	for (int v: adj[u]) {
		if (v == p) continue;
		if (!vis[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		} else if (onStack[v]) {
			low[u] = min(low[u], disc[v]);
		}
	}
	if (low[u] == disc[u]) {
		vi tmp;
		int v = u;
		do {
			v = st.top(); st.pop();
			tmp.pb(v);
			onStack[v] = 0;
		} while (v != u);
		if (tmp.size() != 1) {
			vi nx;
			for (int i: tmp)
				if (mrk[i] == 1) {
					nx.pb(i);
					mrk[i] = 2;
				}
			for (int i: cand)
				mrk[i]--;
			cand = nx;
		}
	}
}

void Link(int a, int b) {
	if (cand.empty()) return;
	adj[a].pb(b);
	adj[b].pb(a);
	if (qry(a) == qry(b) && cycle == 0)
		tarjan(a, -1);
	if (qry(a) == qry(b))
		cycle++;
	if (cycle > 1) {
		cand = {};
		return;
	}
	cnt[deg[a]]--;
	cnt[deg[b]]--;
	deg[a]++, deg[b]++;
	cnt[min(4,deg[a])]++;
	cnt[min(4,deg[b])]++;
	if (cnt[4] > 1) {
		cand = {};
		return;
	}
	if (deg[a] > deg[b])
		swap(a, b);
	if (deg[b] == 3) do3(b);
	if (deg[a] == 3) do3(a);
	if (deg[b] == 4) {
		if (!mrk[b]) {
			cand = {};
			return;
		}
		memset(mrk, 0, sizeof mrk);
		mrk[b] = 1;
		cand = {b};
	}
	join(a, b);
}

int CountCritical() {
	return cand.size();
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23800 KB Output is correct
2 Correct 31 ms 28032 KB Output is correct
3 Incorrect 30 ms 27896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 55252 KB Output is correct
2 Incorrect 833 ms 67992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23800 KB Output is correct
2 Correct 31 ms 28032 KB Output is correct
3 Incorrect 30 ms 27896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23800 KB Output is correct
2 Correct 31 ms 28032 KB Output is correct
3 Incorrect 30 ms 27896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23800 KB Output is correct
2 Correct 31 ms 28032 KB Output is correct
3 Incorrect 30 ms 27896 KB Output isn't correct
4 Halted 0 ms 0 KB -