oj.uz

답안 #105074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
105074 2019-04-10T13:39:28 Z eriksuenderhauf 낙하산 고리들 (IOI12_rings) C++11
37 / 100
 1853 ms 102540 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) {
		if (!mrk[a] && !mrk[b])
			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;
	}
	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 26 ms 23936 KB Output is correct
2 Correct 35 ms 28032 KB Output is correct
3 Correct 29 ms 28024 KB Output is correct
4 Correct 30 ms 23936 KB Output is correct
5 Correct 34 ms 24056 KB Output is correct
6 Correct 29 ms 24448 KB Output is correct
7 Correct 26 ms 23928 KB Output is correct
8 Correct 28 ms 24056 KB Output is correct
9 Correct 29 ms 24192 KB Output is correct
10 Correct 27 ms 24192 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 656 ms 48260 KB Output is correct
2 Correct 1241 ms 62148 KB Output is correct
3 Correct 320 ms 39912 KB Output is correct
4 Correct 1509 ms 72380 KB Output is correct
5 Correct 1548 ms 76008 KB Output is correct
6 Correct 1853 ms 102540 KB Output is correct
7 Correct 332 ms 40164 KB Output is correct
8 Correct 1442 ms 67864 KB Output is correct
9 Correct 1506 ms 70852 KB Output is correct
10 Correct 996 ms 70884 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 23936 KB Output is correct
2 Correct 35 ms 28032 KB Output is correct
3 Correct 29 ms 28024 KB Output is correct
4 Correct 30 ms 23936 KB Output is correct
5 Correct 34 ms 24056 KB Output is correct
6 Correct 29 ms 24448 KB Output is correct
7 Correct 26 ms 23928 KB Output is correct
8 Correct 28 ms 24056 KB Output is correct
9 Correct 29 ms 24192 KB Output is correct
10 Correct 27 ms 24192 KB Output is correct
11 Incorrect 32 ms 28012 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 23936 KB Output is correct
2 Correct 35 ms 28032 KB Output is correct
3 Correct 29 ms 28024 KB Output is correct
4 Correct 30 ms 23936 KB Output is correct
5 Correct 34 ms 24056 KB Output is correct
6 Correct 29 ms 24448 KB Output is correct
7 Correct 26 ms 23928 KB Output is correct
8 Correct 28 ms 24056 KB Output is correct
9 Correct 29 ms 24192 KB Output is correct
10 Correct 27 ms 24192 KB Output is correct
11 Incorrect 32 ms 28012 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 23936 KB Output is correct
2 Correct 35 ms 28032 KB Output is correct
3 Correct 29 ms 28024 KB Output is correct
4 Correct 30 ms 23936 KB Output is correct
5 Correct 34 ms 24056 KB Output is correct
6 Correct 29 ms 24448 KB Output is correct
7 Correct 26 ms 23928 KB Output is correct
8 Correct 28 ms 24056 KB Output is correct
9 Correct 29 ms 24192 KB Output is correct
10 Correct 27 ms 24192 KB Output is correct
11 Correct 656 ms 48260 KB Output is correct
12 Correct 1241 ms 62148 KB Output is correct
13 Correct 320 ms 39912 KB Output is correct
14 Correct 1509 ms 72380 KB Output is correct
15 Correct 1548 ms 76008 KB Output is correct
16 Correct 1853 ms 102540 KB Output is correct
17 Correct 332 ms 40164 KB Output is correct
18 Correct 1442 ms 67864 KB Output is correct
19 Correct 1506 ms 70852 KB Output is correct
20 Correct 996 ms 70884 KB Output is correct
21 Incorrect 32 ms 28012 KB Output isn't correct
22 Halted 0 ms 0 KB -