Submission #503776

#	Time	Username	Problem	Language	Result	Execution time	Memory
503776		rainboy	Wells (CEOI21_wells)	C11	18 / 100	1 ms	212 KiB

wells

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

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

	if (d == 0)
		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 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, ans, x;

	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++) {
		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 && type[i] == 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 && type[i] == 1) {
				good = 0;
				break;
			}
		}
		if (!good)
			continue;
		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;
		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;
				}
			}
		if (check()) {
			yes = 1;
			ans = (ans + x) % MD;
		}
	}
	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:109:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
wells.c:116:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

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