oj.uz

Submission #105072

# Submission time Handle Problem Language Result Execution time Memory
105072 2019-04-10T13:18:21 Z eriksuenderhauf Parachute rings (IOI12_rings) C++11
0 / 100
 1819 ms 102352 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;
	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))
		cycle++;
	/*if (cycle > 1) {
		cout << "k\n";
		cand = {};
		return;
	}*/
	cnt[deg[a]]--;
	cnt[deg[b]]--;
	deg[a]++, deg[b]++;
	cnt[deg[a]]++;
	cnt[deg[b]]++;
	if (cnt[4] > 1) {
		//cout << "ok\n";
		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 23 ms 23808 KB Output is correct
2 Correct 33 ms 27904 KB Output is correct
3 Correct 33 ms 28024 KB Output is correct
4 Correct 27 ms 23932 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24448 KB Output is correct
7 Correct 23 ms 23936 KB Output is correct
8 Incorrect 24 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 581 ms 48540 KB Output is correct
2 Correct 1227 ms 62500 KB Output is correct
3 Correct 296 ms 40036 KB Output is correct
4 Correct 1622 ms 72484 KB Output is correct
5 Correct 1625 ms 76036 KB Output is correct
6 Correct 1819 ms 102352 KB Output is correct
7 Correct 268 ms 40292 KB Output is correct
8 Correct 1473 ms 68044 KB Output is correct
9 Correct 1611 ms 71004 KB Output is correct
10 Incorrect 961 ms 71168 KB Output isn't correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 33 ms 27904 KB Output is correct
3 Correct 33 ms 28024 KB Output is correct
4 Correct 27 ms 23932 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24448 KB Output is correct
7 Correct 23 ms 23936 KB Output is correct
8 Incorrect 24 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 23 ms 23808 KB Output is correct
2 Correct 33 ms 27904 KB Output is correct
3 Correct 33 ms 28024 KB Output is correct
4 Correct 27 ms 23932 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24448 KB Output is correct
7 Correct 23 ms 23936 KB Output is correct
8 Incorrect 24 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 23 ms 23808 KB Output is correct
2 Correct 33 ms 27904 KB Output is correct
3 Correct 33 ms 28024 KB Output is correct
4 Correct 27 ms 23932 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 26 ms 24448 KB Output is correct
7 Correct 23 ms 23936 KB Output is correct
8 Incorrect 24 ms 24064 KB Output isn't correct
9 Halted 0 ms 0 KB -