답안 #23658 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
23658	2017-05-17T22:17:09 Z	Hiasat	낙하산 고리들 (IOI12_rings)	C++14	55 / 100	4000 ms	114556 KB

rings

#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 wat = 0;
	int total = 0;
	bool can = true;
	for (int i = 0 ; i < N; ++i) {
		if (find(i) == i) {
			if (freq[i][4] > 1){
				can = false;
				continue;
			}
			if (freq[i][4]) {

				if (check(big[i][4], -1)){
					res++;
				}
				if(res == 0)
					can = false;
				wat++;
			} else if (freq[i][3]) {

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

					res++;
				}
				for (int j = 0 ; j < adj[big[i][3]].size(); j++) {
					int v = adj[big[i][3]][j];
					if (check(v, -1)) {
						res++;
					}
				}
				if(res == 0)
					can = false;
				wat++;
			} else {
				if(sz[i] > 0 && E[i] != sz[i]-1){
					wat++;
				}
				if(sz[i] && E[i] == sz[i])
					res = sz[find(i)];
				else if(sz[i] && E[i] == sz[i]-1){
					total += sz[find(i)];
				}else can = false;
				
			}
			
		}
	}
	if(wat == 0)
		res += total;
	if (!can || wat > 1)
		res = 0;
	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:112:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0 ; j < adj[big[i][3]].size(); j++) {
                      ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	Output is correct
2	Correct	25 ms	24444 KB	Output is correct
3	Correct	26 ms	24568 KB	Output is correct
4	Correct	23 ms	24568 KB	Output is correct
5	Correct	24 ms	24568 KB	Output is correct
6	Correct	25 ms	24568 KB	Output is correct
7	Correct	23 ms	24568 KB	Output is correct
8	Correct	24 ms	24568 KB	Output is correct
9	Correct	27 ms	24624 KB	Output is correct
10	Correct	25 ms	24624 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	823 ms	69060 KB	Output is correct
2	Correct	1711 ms	96312 KB	Output is correct
3	Correct	2016 ms	111116 KB	Output is correct
4	Correct	2168 ms	111116 KB	Output is correct
5	Correct	2160 ms	111116 KB	Output is correct
6	Correct	2113 ms	111116 KB	Output is correct
7	Correct	1879 ms	111116 KB	Output is correct
8	Correct	2105 ms	111116 KB	Output is correct
9	Correct	2295 ms	114556 KB	Output is correct
10	Correct	1362 ms	114556 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	Output is correct
2	Correct	25 ms	24444 KB	Output is correct
3	Correct	26 ms	24568 KB	Output is correct
4	Correct	23 ms	24568 KB	Output is correct
5	Correct	24 ms	24568 KB	Output is correct
6	Correct	25 ms	24568 KB	Output is correct
7	Correct	23 ms	24568 KB	Output is correct
8	Correct	24 ms	24568 KB	Output is correct
9	Correct	27 ms	24624 KB	Output is correct
10	Correct	25 ms	24624 KB	Output is correct
11	Correct	28 ms	114556 KB	Output is correct
12	Correct	38 ms	114556 KB	Output is correct
13	Correct	38 ms	114556 KB	Output is correct
14	Correct	44 ms	114556 KB	Output is correct
15	Correct	52 ms	114556 KB	Output is correct
16	Correct	39 ms	114556 KB	Output is correct
17	Correct	40 ms	114556 KB	Output is correct
18	Correct	58 ms	114556 KB	Output is correct
19	Correct	35 ms	114556 KB	Output is correct
20	Correct	39 ms	114556 KB	Output is correct

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	Output is correct
2	Correct	25 ms	24444 KB	Output is correct
3	Correct	26 ms	24568 KB	Output is correct
4	Correct	23 ms	24568 KB	Output is correct
5	Correct	24 ms	24568 KB	Output is correct
6	Correct	25 ms	24568 KB	Output is correct
7	Correct	23 ms	24568 KB	Output is correct
8	Correct	24 ms	24568 KB	Output is correct
9	Correct	27 ms	24624 KB	Output is correct
10	Correct	25 ms	24624 KB	Output is correct
11	Correct	28 ms	114556 KB	Output is correct
12	Correct	38 ms	114556 KB	Output is correct
13	Correct	38 ms	114556 KB	Output is correct
14	Correct	44 ms	114556 KB	Output is correct
15	Correct	52 ms	114556 KB	Output is correct
16	Correct	39 ms	114556 KB	Output is correct
17	Correct	40 ms	114556 KB	Output is correct
18	Correct	58 ms	114556 KB	Output is correct
19	Correct	35 ms	114556 KB	Output is correct
20	Correct	39 ms	114556 KB	Output is correct
21	Execution timed out	4017 ms	114556 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	Output is correct
2	Correct	25 ms	24444 KB	Output is correct
3	Correct	26 ms	24568 KB	Output is correct
4	Correct	23 ms	24568 KB	Output is correct
5	Correct	24 ms	24568 KB	Output is correct
6	Correct	25 ms	24568 KB	Output is correct
7	Correct	23 ms	24568 KB	Output is correct
8	Correct	24 ms	24568 KB	Output is correct
9	Correct	27 ms	24624 KB	Output is correct
10	Correct	25 ms	24624 KB	Output is correct
11	Correct	823 ms	69060 KB	Output is correct
12	Correct	1711 ms	96312 KB	Output is correct
13	Correct	2016 ms	111116 KB	Output is correct
14	Correct	2168 ms	111116 KB	Output is correct
15	Correct	2160 ms	111116 KB	Output is correct
16	Correct	2113 ms	111116 KB	Output is correct
17	Correct	1879 ms	111116 KB	Output is correct
18	Correct	2105 ms	111116 KB	Output is correct
19	Correct	2295 ms	114556 KB	Output is correct
20	Correct	1362 ms	114556 KB	Output is correct
21	Correct	28 ms	114556 KB	Output is correct
22	Correct	38 ms	114556 KB	Output is correct
23	Correct	38 ms	114556 KB	Output is correct
24	Correct	44 ms	114556 KB	Output is correct
25	Correct	52 ms	114556 KB	Output is correct
26	Correct	39 ms	114556 KB	Output is correct
27	Correct	40 ms	114556 KB	Output is correct
28	Correct	58 ms	114556 KB	Output is correct
29	Correct	35 ms	114556 KB	Output is correct
30	Correct	39 ms	114556 KB	Output is correct
31	Execution timed out	4017 ms	114556 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #23658

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 0 / 14.0

Subtask #5 0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
0 / 14.0

Subtask #5
0 / 31.0