Submission #503796

#	Time	Username	Problem	Language	Result	Execution time	Memory
503796		rainboy	Wells (CEOI21_wells)	C11	30 / 100	1 ms	428 KiB

wells

/* https://hsin.hr/ceoi/competition/ceoi2021_day2_editorial.pdf */
#include <stdio.h>
#include <stdlib.h>

#define N	10000
#define MD	1000000007
#define INF	0x3f3f3f3f

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 dfs3(int p, int i, int d) {
	int o, x;

	if (d == 0 || type[i] == -1)
		return 1;
	x = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			x = (long long) x * dfs3(i, j, d - 1) % MD;
	}
	return (x + 1) % MD;
}

int dp[N], dq[N], dr[N];

int dfs4(int p, int i) {
	int o, p1, p2;

	dp[i] = -INF, dq[i] = 0, dr[i] = -1, p1 = p2 = -INF;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && (!path[j] && type[j] == 1)) {
			if (!dfs4(i, j))
				return 0;
			dp[i] = max(dp[i], dp[j]);
			if (p1 < dp[j])
				p2 = p1, p1 = dp[j];
			else if (p2 < dp[j])
				p2 = dp[j];
			if (cc[i] == 0 && dq[i] + 1 + dq[j] >= k - 1)
				return 0;
			dq[i] = max(dq[i], dq[j] + 1);
			if (dr[j] != -1)
				dr[i] = dr[j] + 1;
		}
	}
	if (cc[i] == 1)
		dp[i] = hh[i], dq[i] = -1, dr[i] = 0;
	else if (p2 != -INF && dr[i] * 2 <= k - 1 && dr[i] * 2 + p1 + p2 >= k - 1)
		return 0;
	return 1;
}

int ii[N];
int yes, ans;

void try(int r) {
	int g, gl, gr, i, d, h, good, x;

	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 && type[i] == 1) {
			good = 0;
			break;
		}
	}
	if (!good)
		return;
	for (g = gr + 1; g < l; g++) {
		i = ii[g], h = k - 1 - (g - gr);
		if (l - 1 - g + h >= k && type[i] == 1) {
			good = 0;
			break;
		}
	}
	if (!good)
		return;
	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)
		return;
	x = 1;
	for (i = 0; i < n; i++)
		if (!path[i] && type[i] == 0 && (path[pp[i]] || type[pp[i]] == 1)) {
			g = gg[i], d = dd[i];
			if (g + dd[i] + hh[i] >= k - 1) {
				if (g >= gl)
					continue;
				x = (long long) x * dfs3(pp[i], i, k - 1 - (g + dd[i])) % MD;
			} else {
				if (g <= gr)
					continue;
				x = (long long) x * dfs3(pp[i], i, k - 1 - (l - 1 - g + dd[i])) % MD;
			}
		}
	for (g = 0; g < l; g++)
		if (type[ii[g]] == 1 && !dfs4(-1, ii[g]))
			return;
	yes = 1, ans = (ans + x) % MD;
}

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

	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, ans = 0;
	for (r = 0; r < k; r++)
		try(r);
	if (yes) {
		printf("YES\n");
		for (i = 0; i < n; i++)
			if (!path[i] && type[i] == -1)
				ans = ans * 2 % MD;
		printf("%d\n", ans);
	} else {
		printf("NO\n");
		printf("0\n");
	}
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 30 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30