oj.uz

답안 #23654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
23654 2017-05-17T21:50:27 Z Hiasat 낙하산 고리들 (IOI12_rings) C++14
0 / 100
 2588 ms 111204 KB 
#include <bits/stdc++.h>

using namespace std;
int N;

int dsu[1000001], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], vsId;

vector<int> adj[1000001];

bool block[1000001];

bool fn(int u, int p) {
	if (vis[u] == vsId) {
		return false;
	}
	if (!block[u] && in[u] > 2)
		return false;
	vis[u] = vsId;
	for (int i = 0; i < adj[u].size(); ++i) {
		int v = adj[u][i];
		if (v == p || block[v])
			continue;
		if (block[u] && vis[v] == vsId)
			continue;
		if (!fn(v, u))
			return false;
	}
	return true;
}
bool check(int u , int p) {
	block[u] = 1;
	vsId++;
	for (int i = 0; i < adj[u].size(); ++i) {
		in[adj[u][i]]--;
	}
	bool res = fn(u, p);
	for (int i = 0; i < adj[u].size(); ++i) {
		in[adj[u][i]]++;
	}
	block[u] = 0;
	return res;
}
void Init(int N_) {
	N = N_;
	for (int i = 0; i < N; ++i) {
		dsu[i] = i;
		freq[i][0] = 1;
		E[i] = 0;
		sz[i] = 1;
	}
}

int find(int u) {
	return dsu[u] == u ? u : dsu[u] = find(dsu[u]);
}

void Link(int A, int B) {
	adj[A].push_back(B);
	adj[B].push_back(A);
	freq[find(A)][in[A]]--;
	freq[find(B)][in[B]]--;
	in[A]++, in[B]++;
	in[A] = min(in[A], 4);
	in[B] = min(in[B], 4);
	freq[find(A)][in[A]]++;
	freq[find(B)][in[B]]++;
	if (find(A) != find(B)) {
		for (int i = 0 ; i <= 4  ; i++) {
			if (in[A] == i) {
				big[find(A)][i] = A;
			}
			if (in[B] == i) {
				big[find(B)][i] = B;
			}
		}
		E[find(B)] += E[find(A)];
		sz[find(B)] += sz[find(A)];
		for (int i = 0; i <= 4; ++i) {
			big[find(B)][i] = max(big[find(B)][i], big[find(A)][i]);
			freq[find(B)][i] += freq[find(A)][i];
		}
		dsu[find(A)] = find(B);
	}
	E[find(B)]++;
}

int CountCritical() {
	int res = 0;
	int total = 0;
	int wat = 0;
	for (int i = 0 ; i < N; ++i) {
		if (find(i) == i) {
			if (freq[i][4] > 1)
				continue;
			int cnt = 0;
			if (freq[i][4]) {
				if (check(big[i][4], -1))
					cnt++;
				wat++;
			} else if (freq[i][3]) {

				if (check(big[i][3], -1)) {

					cnt++;
				}
				for (int j = 0 ; j < adj[big[i][3]].size(); j++) {
					int v = adj[big[i][3]][j];
					if (check(v, -1)) {
						cnt++;
					}
				}
				wat++;
			} else {
				total += sz[find(i)];
			}
			res += cnt;
		}
	}
	if (wat > 1)
		res = 0;
	else if (wat == 0)
		res += total;
	return res;
}

Compilation message

rings.cpp: In function 'bool fn(int, int)':
rings.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
rings.cpp: In function 'bool check(int, int)':
rings.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
rings.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:106:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0 ; j < adj[big[i][3]].size(); j++) {
                      ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 26 ms 24444 KB Output is correct
3 Correct 26 ms 24484 KB Output is correct
4 Incorrect 22 ms 24484 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 821 ms 68996 KB Output is correct
2 Correct 1663 ms 96408 KB Output is correct
3 Correct 2274 ms 111204 KB Output is correct
4 Incorrect 2588 ms 111204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 26 ms 24444 KB Output is correct
3 Correct 26 ms 24484 KB Output is correct
4 Incorrect 22 ms 24484 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 26 ms 24444 KB Output is correct
3 Correct 26 ms 24484 KB Output is correct
4 Incorrect 22 ms 24484 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 26 ms 24444 KB Output is correct
3 Correct 26 ms 24484 KB Output is correct
4 Incorrect 22 ms 24484 KB Output isn't correct
5 Halted 0 ms 0 KB -