Submission #393195

#	Time	Username	Problem	Language	Result	Execution time	Memory
393195		rainboy	Uzastopni (COCI15_uzastopni)	C11	160 / 160	37 ms	2300 KiB

uzastopni

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

#define N	10000
#define A	100

int *ej[N], eo[N];

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

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

int aa[N]; char dp[N][A];

void dfs(int i) {
	static char can[A][A];
	int o, a, b;

	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j);
	}
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		for (a = 0; a <= aa[j]; a++)
			if (dp[j][a])
				for (b = aa[j]; b < A; b++)
					if (dp[j][b])
						can[a][b] = 1;
	}
	dp[i][aa[i]] = 1;
	for (a = aa[i]; a + 1 < A; a++)
		if (dp[i][a])
			for (b = a + 1; b < A; b++)
				if (can[a + 1][b])
					dp[i][b] = 1;
	for (b = aa[i]; b > 0; b--)
		if (dp[i][b])
			for (a = b - 1; a >= 0; a--)
				if (can[a][b - 1])
					dp[i][a] = 1;
	for (a = 0; a < A; a++)
		memset(can[a] + a, 0, (A - a) * sizeof *can[a]);
}

int main() {
	int n, h, i, j, a, k, l;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]), aa[i]--;
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j);
	}
	dfs(0);
	k = l = 0;
	for (a = 0; a < A; a++)
		if (dp[0][a]) {
			if (a <= aa[0])
				k++;
			if (a >= aa[0])
				l++;
		}
	printf("%d\n", k * l);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 160 / 160