oj.uz

답안 #105068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
105068 2019-04-10T13:02:53 Z eriksuenderhauf 낙하산 고리들 (IOI12_rings) C++11
0 / 100
 746 ms 57300 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 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[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

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 29 ms 28032 KB Output is correct
3 Incorrect 31 ms 28024 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 574 ms 48552 KB Output is correct
2 Incorrect 746 ms 57300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 29 ms 28032 KB Output is correct
3 Incorrect 31 ms 28024 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 29 ms 28032 KB Output is correct
3 Incorrect 31 ms 28024 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 29 ms 28032 KB Output is correct
3 Incorrect 31 ms 28024 KB Output isn't correct
4 Halted 0 ms 0 KB -