oj.uz

Submission #155715

# Submission time Handle Problem Language Result Execution time Memory
155715 2019-09-30T04:01:58 Z Fischer Museum (CEOI17_museum) C++11
45 / 100
 3000 ms 784188 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<<1], head[maxn];
int to[maxn<<1], value[maxn<<1];

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

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:33: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:37: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 638 ms 783420 KB Output is correct
2 Correct 637 ms 783508 KB Output is correct
3 Correct 638 ms 783412 KB Output is correct
4 Correct 663 ms 783436 KB Output is correct
5 Correct 642 ms 783640 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 783788 KB Output is correct
2 Correct 666 ms 783752 KB Output is correct
3 Correct 1854 ms 784188 KB Output is correct
4 Correct 1115 ms 783896 KB Output is correct
5 Correct 755 ms 783748 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 783788 KB Output is correct
2 Correct 666 ms 783752 KB Output is correct
3 Correct 1854 ms 784188 KB Output is correct
4 Correct 1115 ms 783896 KB Output is correct
5 Correct 755 ms 783748 KB Output is correct
6 Correct 706 ms 783916 KB Output is correct
7 Correct 1591 ms 783976 KB Output is correct
8 Execution timed out 3056 ms 783864 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 783420 KB Output is correct
2 Correct 637 ms 783508 KB Output is correct
3 Correct 638 ms 783412 KB Output is correct
4 Correct 663 ms 783436 KB Output is correct
5 Correct 642 ms 783640 KB Output is correct
6 Correct 722 ms 783788 KB Output is correct
7 Correct 666 ms 783752 KB Output is correct
8 Correct 1854 ms 784188 KB Output is correct
9 Correct 1115 ms 783896 KB Output is correct
10 Correct 755 ms 783748 KB Output is correct
11 Correct 706 ms 783916 KB Output is correct
12 Correct 1591 ms 783976 KB Output is correct
13 Execution timed out 3056 ms 783864 KB Time limit exceeded
14 Halted 0 ms 0 KB -