oj.uz

Submission #105083

# Submission time Handle Problem Language Result Execution time Memory
105083 2019-04-10T13:51:23 Z eriksuenderhauf Parachute rings (IOI12_rings) C++11
0 / 100
 1770 ms 102580 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;
int par2[MAXN];

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 dfs(int u, int p) {
	par2[u] = p;
	for (int v: adj[u])
		if (v != p)
			dfs(v, u);
}

void Link(int a, int b) {
	if (cand.empty()) return;
	int delta = 0;
	if (qry(a) == qry(b) && cycle == 0) {
		//tarjan(a, -1);
		dfs(a, -1);
		vi tmp = {a};
		int u = b;
		while (u != a) {
			tmp.pb(u);
			u = par2[u];
		}
		vi nx;
		for (int i: tmp)
			if (mrk[i] == 1) {
				nx.pb(i);
				mrk[i] = 2;
			}
		for (int i: cand)
			mrk[i]--;
		cand = nx;
	}
	adj[a].pb(b);
	adj[b].pb(a);
	if (qry(a) == qry(b)) {
		delta++;
		cycle++;
	}
	cnt[deg[a]]--;
	cnt[deg[b]]--;
	deg[a]++, deg[b]++;
	cnt[deg[a]]++;
	cnt[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};
	}
	if (cycle > 1 && delta > 0) {
		if (!mrk[a] && !mrk[b]) {
			vi tmp;
			for (int i: adj[a])
				for (int j: adj[b])
					if (i == j)
						tmp.pb(i);
			if (!tmp.empty() && !mrk[tmp[0]])
				cand = {};
		} else if (mrk[a] && mrk[b]) {
			cand = {a, b};
			memset(mrk, 0, sizeof mrk);
			mrk[a] = 1, mrk[b] = 1;
		} else {
			if (mrk[a]) {
				memset(mrk, 0, sizeof mrk);
				mrk[a] = 1;
				cand = {a};
			} else {
				memset(mrk, 0, sizeof mrk);
				mrk[b] = 1;
				cand = {b};
			}
		}
		return;
	}
	join(a, b);
}

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 30 ms 27896 KB Output is correct
3 Correct 31 ms 28024 KB Output is correct
4 Correct 30 ms 23928 KB Output is correct
5 Correct 27 ms 24192 KB Output is correct
6 Correct 30 ms 24448 KB Output is correct
7 Correct 24 ms 23936 KB Output is correct
8 Incorrect 32 ms 24064 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 48464 KB Output is correct
2 Correct 1207 ms 62428 KB Output is correct
3 Correct 330 ms 40144 KB Output is correct
4 Correct 1560 ms 72616 KB Output is correct
5 Correct 1639 ms 76320 KB Output is correct
6 Correct 1770 ms 102580 KB Output is correct
7 Correct 322 ms 40292 KB Output is correct
8 Correct 1485 ms 67988 KB Output is correct
9 Correct 1546 ms 71084 KB Output is correct
10 Incorrect 984 ms 71052 KB Output isn't correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 30 ms 27896 KB Output is correct
3 Correct 31 ms 28024 KB Output is correct
4 Correct 30 ms 23928 KB Output is correct
5 Correct 27 ms 24192 KB Output is correct
6 Correct 30 ms 24448 KB Output is correct
7 Correct 24 ms 23936 KB Output is correct
8 Incorrect 32 ms 24064 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 30 ms 27896 KB Output is correct
3 Correct 31 ms 28024 KB Output is correct
4 Correct 30 ms 23928 KB Output is correct
5 Correct 27 ms 24192 KB Output is correct
6 Correct 30 ms 24448 KB Output is correct
7 Correct 24 ms 23936 KB Output is correct
8 Incorrect 32 ms 24064 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 30 ms 27896 KB Output is correct
3 Correct 31 ms 28024 KB Output is correct
4 Correct 30 ms 23928 KB Output is correct
5 Correct 27 ms 24192 KB Output is correct
6 Correct 30 ms 24448 KB Output is correct
7 Correct 24 ms 23936 KB Output is correct
8 Incorrect 32 ms 24064 KB Output isn't correct
9 Halted 0 ms 0 KB -