oj.uz

Submission #741221

# Submission time Handle Problem Language Result Execution time Memory
741221 2023-05-13T21:38:56 Z rainboy Museum (CEOI17_museum) C
100 / 100
 205 ms 2248 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	10000
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

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

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

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

int *dp[N], *dq[N], sz[N];

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

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

		if (j != p) {
			dfs(i, c, j);
			sz[i] += sz[j];
		}
	}
	dp[i] = (int *) malloc((sz[i] + 1) * sizeof *dp[i]);
	dq[i] = (int *) malloc((sz[i] + 1) * sizeof *dq[i]);
	memset(dp[i], 0x3f, (sz[i] + 1) * sizeof *dp[i]);
	memset(dq[i], 0x3f, (sz[i] + 1) * sizeof *dq[i]);
	sz[i] = 1;
	dp[i][0] = 0, dq[i][0] = 0, dp[i][1] = 0, dq[i][1] = 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			for (s1 = sz[i]; s1 > 0; s1--)
				for (s2 = sz[j]; s2 > 0; s2--) {
					s = s1 + s2;
					dp[i][s] = min(dp[i][s], dp[i][s1] + dp[j][s2]);
					dq[i][s] = min(dq[i][s], min(dq[i][s1] + dp[j][s2], dp[i][s1] + dq[j][s2]));
				}
			free(dp[j]), free(dq[j]);
			sz[i] += sz[j];
		}
	}
	for (s = 1; s <= sz[i]; s++)
		dp[i][s] += c_ * 2, dq[i][s] += c_;
}

int main() {
	int n, k, r, h, i, j, c;

	scanf("%d%d%d", &n, &k, &r), r--;
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ec[i] = (int *) malloc(2 * sizeof *ec[i]);
	}
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d%d", &i, &j, &c), i--, j--;
		append(i, j, c), append(j, i, c);
	}
	dfs(-1, 0, r);
	printf("%d\n", dq[r][k]);
	return 0;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 1716 KB Output is correct
2 Correct 108 ms 1764 KB Output is correct
3 Correct 130 ms 2192 KB Output is correct
4 Correct 115 ms 1828 KB Output is correct
5 Correct 118 ms 1832 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 1716 KB Output is correct
2 Correct 108 ms 1764 KB Output is correct
3 Correct 130 ms 2192 KB Output is correct
4 Correct 115 ms 1828 KB Output is correct
5 Correct 118 ms 1832 KB Output is correct
6 Correct 110 ms 1712 KB Output is correct
7 Correct 123 ms 1972 KB Output is correct
8 Correct 205 ms 2132 KB Output is correct
9 Correct 146 ms 1916 KB Output is correct
10 Correct 117 ms 1820 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 110 ms 1716 KB Output is correct
7 Correct 108 ms 1764 KB Output is correct
8 Correct 130 ms 2192 KB Output is correct
9 Correct 115 ms 1828 KB Output is correct
10 Correct 118 ms 1832 KB Output is correct
11 Correct 110 ms 1712 KB Output is correct
12 Correct 123 ms 1972 KB Output is correct
13 Correct 205 ms 2132 KB Output is correct
14 Correct 146 ms 1916 KB Output is correct
15 Correct 117 ms 1820 KB Output is correct
16 Correct 106 ms 1656 KB Output is correct
17 Correct 133 ms 1612 KB Output is correct
18 Correct 120 ms 1984 KB Output is correct
19 Correct 179 ms 2028 KB Output is correct
20 Correct 115 ms 1828 KB Output is correct
21 Correct 137 ms 1960 KB Output is correct
22 Correct 106 ms 1720 KB Output is correct
23 Correct 184 ms 2008 KB Output is correct
24 Correct 119 ms 1864 KB Output is correct
25 Correct 132 ms 2248 KB Output is correct