oj.uz

Submission #476124

# Submission time Handle Problem Language Result Execution time Memory
476124 2021-09-24T20:11:36 Z rainboy Dostavljač (COCI18_dostavljac) C
140 / 140
 8 ms 2500 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	500

int max(int a, int b) { return a > b ? a : b; }

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], dp[N][N * 3 + 1][2], sz[N];

void dfs(int p, int i) {
	int o, s, s_, s1;

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

		if (j != p) {
			dfs(i, j);
			sz[i] += sz[j];
		}
	}
	for (s = 0; s <= sz[i] * 3; s++)
		dp[i][s][0] = dp[i][s][1] = -1;
	dp[i][0][0] = dp[i][0][1] = 0;
	s_ = 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			for (s = s_ * 3; s >= 0; s--) {
				int w = dp[i][s][0], x = dp[i][s][1];

				for (s1 = 1; s1 <= sz[j] * 3; s1++) {
					int y = dp[j][s1][0], z = dp[j][s1][1];

					if (w != -1 && y != -1)
						dp[i][s + s1][0] = max(dp[i][s + s1][0], w + y);
					if (w != -1 && z != -1)
						dp[i][s + s1][1] = max(dp[i][s + s1][1], w + z);
					if (x != -1 && y != -1)
						dp[i][s + s1][1] = max(dp[i][s + s1][1], x + y);
				}
			}
			s_ += sz[j];
		}
	}
	s_++;
	for (s = s_ * 3; s > 0; s--) {
		int w = dp[i][s - 1][0], x = dp[i][s - 1][1];

		if (w != -1)
			dp[i][s][0] = max(dp[i][s][0], w + aa[i]);
		if (x != -1)
			dp[i][s][1] = max(dp[i][s][1], x + aa[i]);
	}
	if (p != -1)
		for (s = s_ * 3; s >= 0; s--) {
			dp[i][s][0] = s < 2 ? -1 : dp[i][s - 2][0];
			dp[i][s][1] = s < 1 ? -1 : dp[i][s - 1][1];
		}
}

int main() {
	int n, m, h, i, j, s, ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%d", &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), append(j, i);
	}
	dfs(-1, 0);
	ans = 0;
	for (s = 0; s <= m && s <= n * 3; s++)
		ans = max(ans, max(dp[0][s][0], dp[0][s][1]));
	printf("%d\n", ans);
	return 0;
}

Compilation message

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 3 ms 1576 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1996 KB Output is correct
2 Correct 4 ms 2124 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2500 KB Output is correct
2 Correct 8 ms 2348 KB Output is correct