oj.uz

답안 #503753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503753 2022-01-08T20:52:18 Z rainboy Wells (CEOI21_wells) C
0 / 100
 1 ms 332 KB 
/* https://hsin.hr/ceoi/competition/ceoi2021_day2_editorial.pdf */
#include <stdio.h>

#define N	300
#define MD	1000000007

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int pp2[N + 1];

void init() {
	int i;

	pp2[0] = 1;
	for (i = 1; i <= N; i++)
		pp2[i] = pp2[i - 1] * 2 % MD;
}

int mem[(N - 1) * 2], *ptr = mem;
int *ej[N], eo[N], pp[N], cc[N], n, k; char type[N];

int i_, l;

void dfs1(int p, int i, int d) {
	int o;

	pp[i] = p;
	d++;
	if (l < d)
		l = d, i_ = i;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs1(i, j, d);
	}
}

char path[N];
int gg[N], dd[N], hh[N];

void dfs2(int p, int i, int g, int d) {
	int o;

	gg[i] = g, dd[i] = d, hh[i] = 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && !path[j]) {
			dfs2(i, j, g, d + 1);
			hh[i] = max(hh[i], hh[j] + 1);
		}
	}
}

int contains(int a, int b, int r) {
	a %= r, b %= r;
	return a <= b ? a <= r && r <= b : a <= r || r <= b;
}

int check_(int p, int i, int d, int c) {
	int o;

	if (path[i] || type[i] != 1)
		return 1;
	if (cc[i] == 1)
		c++;
	if (--d == 0)
		return c == 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && !check_(i, j, d, c))
			return 0;
	}
	return 1;
}

int check() {
	int i;

	for (i = 0; i < n; i++)
		if (!check_(-1, i, k, 0))
			return 0;
	return 1;
}

int main() {
	static int uu[N - 1], vv[N - 1], ii[N];
	int g, h, i, j, u, v, d, r, yes;

	init();
	scanf("%d%d", &n, &k);
	if (k == 2) {
		printf("YES\n");
		printf("2\n");
		return 0;
	}
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		uu[h] = i, vv[h] = j;
		eo[i]++, eo[j]++;
	}
	for (i = 0; i < n; i++) {
		ej[i] = ptr, ptr += eo[i];
		eo[i] = 0;
	}
	for (h = 0; h < n - 1; h++) {
		i = uu[h], j = vv[h];
		ej[i][eo[i]++] = j, ej[j][eo[j]++] = i;
	}
	i_ = -1, l = -1, dfs1(-1, 0, 0), u = i_;
	i_ = -1, l = -1, dfs1(-1, u, 0), v = i_;
	if (l < k) {
		printf("YES\n");
		printf("%d\n", pp2[n]);
		return 0;
	}
	for (i = v, d = l - 1; i != u; i = pp[i], d--)
		path[ii[d] = i] = 1;
	path[ii[0] = u] = 1;
	for (g = 0; g < l; g++)
		dfs2(-1, ii[g], g, 0);
	for (i = 0; i < n; i++) {
		g = gg[i];
		if (max(g, l - 1 - g) + dd[i] + hh[i] < k - 1)
			type[i] = -1;
		else if (min(g, l - 1 - g) + dd[i] + hh[i] >= k - 1)
			type[i] = 1;
		else
			type[i] = 0;
	}
	yes = 0;
	for (r = 0; r < k; r++) {
		int gl, gr, good;

		gl = r, gr = (l - 1 - r) / k * k + r;
		good = 1;
		for (g = 0; g < gl; g++) {
			i = ii[g], h = k - 1 - (gl - g);
			if (g + h >= k && hh[i] + g >= k - 1) {
				good = 0;
				break;
			}
		}
		if (!good)
			continue;
		for (g = gr + 1; g < l; g++) {
			i = ii[g], h = k - 1 - (g - gr);
			if (l - 1 - g + h >= k && hh[i] + l - 1 - g >= k - 1) {
				good = 0;
				break;
			}
		}
		if (!good)
			continue;
		for (i = 0; i < n; i++)
			cc[i] = -2;
		for (i = 0; i < n; i++) {
			g = gg[i], d = dd[i];
			if (path[i])
				cc[i] = g % k == r ? 1 : 0;
			else if (type[i] == 1) {
				int cl = g >= gl ? ((g + d) % k == r ? 1 : 0) : -1;
				int cr = g <= gr ? ((g - d % k + k) % k == r ? 1 : 0) : -1;

				if (cl != -1 && cr != -1) {
					if (cl != cr) {
						good = 0;
						break;
					}
					cc[i] = cl;
				} else
					cc[i] = cl != -1 ? cl : cr;
			}
		}
		if (!good)
			continue;
		if (check())
			yes = 1;
	}
	if (yes)
		printf("YES\n");
	else
		printf("NO\n");
	printf("0\n");
	return 0;
}

Compilation message

wells.c: In function 'main':
wells.c:94:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
wells.c:101:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Partially correct 0 ms 204 KB Output is partially correct
3 Partially correct 0 ms 204 KB Output is partially correct
4 Partially correct 0 ms 204 KB Output is partially correct
5 Partially correct 0 ms 204 KB Output is partially correct
6 Partially correct 0 ms 204 KB Output is partially correct
7 Correct 0 ms 204 KB Output is correct
8 Partially correct 1 ms 248 KB Output is partially correct
9 Partially correct 0 ms 204 KB Output is partially correct
10 Correct 0 ms 204 KB Output is correct
11 Partially correct 0 ms 204 KB Output is partially correct
12 Correct 0 ms 204 KB Output is correct
13 Partially correct 0 ms 204 KB Output is partially correct
14 Partially correct 1 ms 204 KB Output is partially correct
15 Partially correct 1 ms 204 KB Output is partially correct
16 Partially correct 1 ms 204 KB Output is partially correct
17 Partially correct 1 ms 204 KB Output is partially correct
18 Partially correct 0 ms 204 KB Output is partially correct
19 Partially correct 0 ms 204 KB Output is partially correct
20 Correct 0 ms 204 KB Output is correct
21 Partially correct 1 ms 280 KB Output is partially correct
22 Partially correct 1 ms 204 KB Output is partially correct
23 Partially correct 1 ms 284 KB Output is partially correct
24 Partially correct 1 ms 280 KB Output is partially correct
25 Partially correct 1 ms 284 KB Output is partially correct
26 Partially correct 1 ms 284 KB Output is partially correct
27 Partially correct 1 ms 268 KB Output is partially correct
28 Correct 1 ms 204 KB Output is correct
29 Partially correct 1 ms 208 KB Output is partially correct
30 Partially correct 0 ms 204 KB Output is partially correct
31 Partially correct 1 ms 288 KB Output is partially correct
32 Correct 1 ms 280 KB Output is correct
33 Partially correct 1 ms 280 KB Output is partially correct
34 Correct 1 ms 280 KB Output is correct
35 Partially correct 0 ms 204 KB Output is partially correct
36 Partially correct 0 ms 204 KB Output is partially correct
37 Partially correct 1 ms 204 KB Output is partially correct
38 Partially correct 1 ms 284 KB Output is partially correct
39 Partially correct 1 ms 280 KB Output is partially correct
40 Partially correct 1 ms 280 KB Output is partially correct
41 Partially correct 0 ms 332 KB Output is partially correct
42 Partially correct 1 ms 284 KB Output is partially correct
43 Partially correct 1 ms 276 KB Output is partially correct
44 Correct 0 ms 204 KB Output is correct
45 Partially correct 0 ms 284 KB Output is partially correct
46 Partially correct 1 ms 216 KB Output is partially correct
47 Partially correct 0 ms 204 KB Output is partially correct
48 Partially correct 1 ms 204 KB Output is partially correct
49 Incorrect 1 ms 212 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Partially correct 0 ms 204 KB Output is partially correct
3 Partially correct 0 ms 204 KB Output is partially correct
4 Partially correct 0 ms 204 KB Output is partially correct
5 Partially correct 0 ms 204 KB Output is partially correct
6 Partially correct 0 ms 204 KB Output is partially correct
7 Correct 0 ms 204 KB Output is correct
8 Partially correct 1 ms 248 KB Output is partially correct
9 Partially correct 0 ms 204 KB Output is partially correct
10 Correct 0 ms 204 KB Output is correct
11 Partially correct 0 ms 204 KB Output is partially correct
12 Correct 0 ms 204 KB Output is correct
13 Partially correct 0 ms 204 KB Output is partially correct
14 Partially correct 1 ms 204 KB Output is partially correct
15 Partially correct 1 ms 204 KB Output is partially correct
16 Partially correct 1 ms 204 KB Output is partially correct
17 Partially correct 1 ms 204 KB Output is partially correct
18 Partially correct 0 ms 204 KB Output is partially correct
19 Partially correct 0 ms 204 KB Output is partially correct
20 Correct 0 ms 204 KB Output is correct
21 Partially correct 1 ms 280 KB Output is partially correct
22 Partially correct 1 ms 204 KB Output is partially correct
23 Partially correct 1 ms 284 KB Output is partially correct
24 Partially correct 1 ms 280 KB Output is partially correct
25 Partially correct 1 ms 284 KB Output is partially correct
26 Partially correct 1 ms 284 KB Output is partially correct
27 Partially correct 1 ms 268 KB Output is partially correct
28 Correct 1 ms 204 KB Output is correct
29 Partially correct 1 ms 208 KB Output is partially correct
30 Partially correct 0 ms 204 KB Output is partially correct
31 Partially correct 1 ms 288 KB Output is partially correct
32 Correct 1 ms 280 KB Output is correct
33 Partially correct 1 ms 280 KB Output is partially correct
34 Correct 1 ms 280 KB Output is correct
35 Partially correct 0 ms 204 KB Output is partially correct
36 Partially correct 0 ms 204 KB Output is partially correct
37 Partially correct 1 ms 204 KB Output is partially correct
38 Partially correct 1 ms 284 KB Output is partially correct
39 Partially correct 1 ms 280 KB Output is partially correct
40 Partially correct 1 ms 280 KB Output is partially correct
41 Partially correct 0 ms 332 KB Output is partially correct
42 Partially correct 1 ms 284 KB Output is partially correct
43 Partially correct 1 ms 276 KB Output is partially correct
44 Correct 0 ms 204 KB Output is correct
45 Partially correct 0 ms 284 KB Output is partially correct
46 Partially correct 1 ms 216 KB Output is partially correct
47 Partially correct 0 ms 204 KB Output is partially correct
48 Partially correct 1 ms 204 KB Output is partially correct
49 Incorrect 1 ms 212 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Partially correct 0 ms 204 KB Output is partially correct
3 Partially correct 0 ms 204 KB Output is partially correct
4 Partially correct 0 ms 204 KB Output is partially correct
5 Partially correct 0 ms 204 KB Output is partially correct
6 Partially correct 0 ms 204 KB Output is partially correct
7 Correct 0 ms 204 KB Output is correct
8 Partially correct 1 ms 248 KB Output is partially correct
9 Partially correct 0 ms 204 KB Output is partially correct
10 Correct 0 ms 204 KB Output is correct
11 Partially correct 0 ms 204 KB Output is partially correct
12 Correct 0 ms 204 KB Output is correct
13 Partially correct 0 ms 204 KB Output is partially correct
14 Partially correct 1 ms 204 KB Output is partially correct
15 Partially correct 1 ms 204 KB Output is partially correct
16 Partially correct 1 ms 204 KB Output is partially correct
17 Partially correct 1 ms 204 KB Output is partially correct
18 Partially correct 0 ms 204 KB Output is partially correct
19 Partially correct 0 ms 204 KB Output is partially correct
20 Correct 0 ms 204 KB Output is correct
21 Partially correct 1 ms 280 KB Output is partially correct
22 Partially correct 1 ms 204 KB Output is partially correct
23 Partially correct 1 ms 284 KB Output is partially correct
24 Partially correct 1 ms 280 KB Output is partially correct
25 Partially correct 1 ms 284 KB Output is partially correct
26 Partially correct 1 ms 284 KB Output is partially correct
27 Partially correct 1 ms 268 KB Output is partially correct
28 Correct 1 ms 204 KB Output is correct
29 Partially correct 1 ms 208 KB Output is partially correct
30 Partially correct 0 ms 204 KB Output is partially correct
31 Partially correct 1 ms 288 KB Output is partially correct
32 Correct 1 ms 280 KB Output is correct
33 Partially correct 1 ms 280 KB Output is partially correct
34 Correct 1 ms 280 KB Output is correct
35 Partially correct 0 ms 204 KB Output is partially correct
36 Partially correct 0 ms 204 KB Output is partially correct
37 Partially correct 1 ms 204 KB Output is partially correct
38 Partially correct 1 ms 284 KB Output is partially correct
39 Partially correct 1 ms 280 KB Output is partially correct
40 Partially correct 1 ms 280 KB Output is partially correct
41 Partially correct 0 ms 332 KB Output is partially correct
42 Partially correct 1 ms 284 KB Output is partially correct
43 Partially correct 1 ms 276 KB Output is partially correct
44 Correct 0 ms 204 KB Output is correct
45 Partially correct 0 ms 284 KB Output is partially correct
46 Partially correct 1 ms 216 KB Output is partially correct
47 Partially correct 0 ms 204 KB Output is partially correct
48 Partially correct 1 ms 204 KB Output is partially correct
49 Incorrect 1 ms 212 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Partially correct 0 ms 204 KB Output is partially correct
3 Partially correct 0 ms 204 KB Output is partially correct
4 Partially correct 0 ms 204 KB Output is partially correct
5 Partially correct 0 ms 204 KB Output is partially correct
6 Partially correct 0 ms 204 KB Output is partially correct
7 Correct 0 ms 204 KB Output is correct
8 Partially correct 1 ms 248 KB Output is partially correct
9 Partially correct 0 ms 204 KB Output is partially correct
10 Correct 0 ms 204 KB Output is correct
11 Partially correct 0 ms 204 KB Output is partially correct
12 Correct 0 ms 204 KB Output is correct
13 Partially correct 0 ms 204 KB Output is partially correct
14 Partially correct 1 ms 204 KB Output is partially correct
15 Partially correct 1 ms 204 KB Output is partially correct
16 Partially correct 1 ms 204 KB Output is partially correct
17 Partially correct 1 ms 204 KB Output is partially correct
18 Partially correct 0 ms 204 KB Output is partially correct
19 Partially correct 0 ms 204 KB Output is partially correct
20 Correct 0 ms 204 KB Output is correct
21 Partially correct 1 ms 280 KB Output is partially correct
22 Partially correct 1 ms 204 KB Output is partially correct
23 Partially correct 1 ms 284 KB Output is partially correct
24 Partially correct 1 ms 280 KB Output is partially correct
25 Partially correct 1 ms 284 KB Output is partially correct
26 Partially correct 1 ms 284 KB Output is partially correct
27 Partially correct 1 ms 268 KB Output is partially correct
28 Correct 1 ms 204 KB Output is correct
29 Partially correct 1 ms 208 KB Output is partially correct
30 Partially correct 0 ms 204 KB Output is partially correct
31 Partially correct 1 ms 288 KB Output is partially correct
32 Correct 1 ms 280 KB Output is correct
33 Partially correct 1 ms 280 KB Output is partially correct
34 Correct 1 ms 280 KB Output is correct
35 Partially correct 0 ms 204 KB Output is partially correct
36 Partially correct 0 ms 204 KB Output is partially correct
37 Partially correct 1 ms 204 KB Output is partially correct
38 Partially correct 1 ms 284 KB Output is partially correct
39 Partially correct 1 ms 280 KB Output is partially correct
40 Partially correct 1 ms 280 KB Output is partially correct
41 Partially correct 0 ms 332 KB Output is partially correct
42 Partially correct 1 ms 284 KB Output is partially correct
43 Partially correct 1 ms 276 KB Output is partially correct
44 Correct 0 ms 204 KB Output is correct
45 Partially correct 0 ms 284 KB Output is partially correct
46 Partially correct 1 ms 216 KB Output is partially correct
47 Partially correct 0 ms 204 KB Output is partially correct
48 Partially correct 1 ms 204 KB Output is partially correct
49 Incorrect 1 ms 212 KB Output isn't correct
50 Halted 0 ms 0 KB -