oj.uz

Submission #393195

# Submission time Handle Problem Language Result Execution time Memory
393195 2021-04-22T23:35:19 Z rainboy Uzastopni (COCI15_uzastopni) C
160 / 160
 37 ms 2300 KB 
#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

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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 288 KB Output is correct
11 Correct 19 ms 1868 KB Output is correct
12 Correct 19 ms 1868 KB Output is correct
13 Correct 22 ms 1856 KB Output is correct
14 Correct 37 ms 2300 KB Output is correct
15 Correct 37 ms 2192 KB Output is correct
16 Correct 37 ms 2260 KB Output is correct
17 Correct 22 ms 1868 KB Output is correct
18 Correct 20 ms 1740 KB Output is correct
19 Correct 19 ms 1740 KB Output is correct
20 Correct 19 ms 1796 KB Output is correct