oj.uz

Submission #155712

# Submission time Handle Problem Language Result Execution time Memory
155712 2019-09-30T03:41:05 Z Fischer Museum (CEOI17_museum) C++
20 / 100
 1438 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 2;
int n, k, x;
int sz[maxn];
int memo[maxn][maxn][2];
int nxt[maxn], head[maxn];
int to[maxn], value[maxn];

void dfs(int x, int p) {
	sz[x] = 1;
	for (int i = head[x]; ~i; i = nxt[i]) {
		int v = to[i];
		if (v == p) continue;
		dfs(v, x);
		sz[x] += sz[v];
	}
	memo[x][1][0] = memo[x][1][1] = 0; 
	for (int i = head[x]; ~i; i = nxt[i]) {
		int v = to[i], w = value[i];
		if (v == p) continue;
		for (int i = min(sz[x], k); i >= 2; --i) {
			for (int j = min(sz[v], i-1); j >= 1; --j) {
				memo[x][i][1] = min(memo[x][i][1],
					min(
						memo[x][i-j][1] + memo[v][j][0] + (w<<1),
						memo[x][i-j][0] + memo[v][j][1] + w
					));
				memo[x][i][0] = min(memo[x][i][0], 
					memo[x][i-j][0] + memo[v][j][0] + (w<<1));
			}
		}
	}
}

int main() {
	scanf("%d %d %d", &n, &k, &x);
	memset(head, -1, sizeof head);
	for (int i = 1; i <= n-1; ++i) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		to[i<<1] = b; 
		value[i<<1] = c; nxt[i<<1] = head[a]; head[a] = i<<1;
		to[i<<1|1] = a; 
		value[i<<1|1] = c; nxt[i<<1|1] = head[b]; head[b] = i<<1|1;
	}
	memset(memo, 63, sizeof memo);
	dfs(x, 0);
	printf("%d\n", memo[x][k][1]);	
	return 0;
}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &k, &x);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 783520 KB Output is correct
2 Correct 644 ms 783480 KB Output is correct
3 Correct 662 ms 783484 KB Output is correct
4 Correct 649 ms 783476 KB Output is correct
5 Correct 645 ms 783484 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1438 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1438 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 783520 KB Output is correct
2 Correct 644 ms 783480 KB Output is correct
3 Correct 662 ms 783484 KB Output is correct
4 Correct 649 ms 783476 KB Output is correct
5 Correct 645 ms 783484 KB Output is correct
6 Runtime error 1438 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -