Submission #544733

#	Time	Username	Problem	Language	Result	Execution time	Memory
544733		rainboy	Cat in a tree (BOI17_catinatree)	C11	100 / 100	87 ms	21428 KiB

catinatree

#include <stdio.h>
#include <stdlib.h>

#define N	200000
#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 *oj[N], oo[N];

void append(int i, int j) {
	int o = oo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		oj[i] = (int *) realloc(oj[i], o * 2 * sizeof *oj[i]);
	oj[i][o] = j;
}

int dp[N], dd1[N], dd2[N], d_;

void dfs(int i) {
	int o, d1, d2;

	d1 = -1, d2 = INF;
	for (o = 0; o < oo[i]; o++) {
		int j = oj[i][o];

		dfs(j);
		dp[i] += dp[j];
		if (dd1[j] != INF)
			dp[i]--, d1 = max(d1, dd1[j]);
		d2 = min(d2, dd2[j]);
	}
	if (d1 != -1 && d1 + d2 >= d_)
		dp[i]++, dd1[i] = d1, dd2[i] = d2;
	else
		dd1[i] = INF, dd2[i] = d2;
	if (dd1[i] >= d_ && dd2[i] >= d_)
		dp[i]++, dd1[i] = 0, dd2[i] = INF;
	if (dd1[i] != INF)
		dd1[i]++;
	if (dd2[i] != INF)
		dd2[i]++;
	if (dd1[i] * 2 >= d_)
		dd2[i] = min(dd2[i], dd1[i]), dd1[i] = INF;
}

int main() {
	int n, i;

	scanf("%d%d", &n, &d_);
	for (i = 0; i < n; i++)
		oj[i] = (int *) malloc(2 * sizeof *oj[i]);
	for (i = 1; i < n; i++) {
		int p;

		scanf("%d", &p);
		append(p, i);
	}
	dfs(0);
	printf("%d\n", dp[0]);
	return 0;
}

Compilation message (stderr)

catinatree.c: In function 'append':
catinatree.c:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   15 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
catinatree.c: In function 'main':
catinatree.c:52:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d%d", &n, &d_);
      |  ^~~~~~~~~~~~~~~~~~~~~~
catinatree.c:58:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d", &p);
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49