oj.uz

답안 #105071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
105071 2019-04-10T13:12:40 Z eriksuenderhauf 낙하산 고리들 (IOI12_rings) C++11
37 / 100
 1840 ms 115376 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) {
		cand = {};
		return;
	}
	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};
	}
	join(a, b);
}

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

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 35 ms 28024 KB Output is correct
3 Correct 32 ms 28008 KB Output is correct
4 Correct 25 ms 23908 KB Output is correct
5 Correct 27 ms 24076 KB Output is correct
6 Correct 29 ms 24412 KB Output is correct
7 Correct 26 ms 23936 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 28 ms 24192 KB Output is correct
10 Correct 30 ms 24192 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 595 ms 48488 KB Output is correct
2 Correct 1235 ms 62464 KB Output is correct
3 Correct 332 ms 52572 KB Output is correct
4 Correct 1609 ms 85728 KB Output is correct
5 Correct 1689 ms 89440 KB Output is correct
6 Correct 1840 ms 115376 KB Output is correct
7 Correct 328 ms 52316 KB Output is correct
8 Correct 1490 ms 80608 KB Output is correct
9 Correct 1732 ms 84300 KB Output is correct
10 Correct 1082 ms 83568 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 35 ms 28024 KB Output is correct
3 Correct 32 ms 28008 KB Output is correct
4 Correct 25 ms 23908 KB Output is correct
5 Correct 27 ms 24076 KB Output is correct
6 Correct 29 ms 24412 KB Output is correct
7 Correct 26 ms 23936 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 28 ms 24192 KB Output is correct
10 Correct 30 ms 24192 KB Output is correct
11 Incorrect 31 ms 24192 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 35 ms 28024 KB Output is correct
3 Correct 32 ms 28008 KB Output is correct
4 Correct 25 ms 23908 KB Output is correct
5 Correct 27 ms 24076 KB Output is correct
6 Correct 29 ms 24412 KB Output is correct
7 Correct 26 ms 23936 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 28 ms 24192 KB Output is correct
10 Correct 30 ms 24192 KB Output is correct
11 Incorrect 31 ms 24192 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 35 ms 28024 KB Output is correct
3 Correct 32 ms 28008 KB Output is correct
4 Correct 25 ms 23908 KB Output is correct
5 Correct 27 ms 24076 KB Output is correct
6 Correct 29 ms 24412 KB Output is correct
7 Correct 26 ms 23936 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 28 ms 24192 KB Output is correct
10 Correct 30 ms 24192 KB Output is correct
11 Correct 595 ms 48488 KB Output is correct
12 Correct 1235 ms 62464 KB Output is correct
13 Correct 332 ms 52572 KB Output is correct
14 Correct 1609 ms 85728 KB Output is correct
15 Correct 1689 ms 89440 KB Output is correct
16 Correct 1840 ms 115376 KB Output is correct
17 Correct 328 ms 52316 KB Output is correct
18 Correct 1490 ms 80608 KB Output is correct
19 Correct 1732 ms 84300 KB Output is correct
20 Correct 1082 ms 83568 KB Output is correct
21 Incorrect 31 ms 24192 KB Output isn't correct
22 Halted 0 ms 0 KB -