oj.uz

Submission #155713

# Submission time Handle Problem Language Result Execution time Memory
155713 2019-09-30T03:42:35 Z Fischer Museum (CEOI17_museum) C++
80 / 100
 3000 ms 784216 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;
	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 685 ms 783484 KB Output is correct
2 Correct 737 ms 783748 KB Output is correct
3 Correct 639 ms 783484 KB Output is correct
4 Correct 647 ms 783404 KB Output is correct
5 Correct 705 ms 783564 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 783864 KB Output is correct
2 Correct 732 ms 784008 KB Output is correct
3 Correct 736 ms 784140 KB Output is correct
4 Correct 782 ms 784028 KB Output is correct
5 Correct 704 ms 783892 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 783864 KB Output is correct
2 Correct 732 ms 784008 KB Output is correct
3 Correct 736 ms 784140 KB Output is correct
4 Correct 782 ms 784028 KB Output is correct
5 Correct 704 ms 783892 KB Output is correct
6 Correct 735 ms 783900 KB Output is correct
7 Correct 720 ms 784216 KB Output is correct
8 Correct 654 ms 783916 KB Output is correct
9 Correct 689 ms 783880 KB Output is correct
10 Correct 698 ms 783936 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 783484 KB Output is correct
2 Correct 737 ms 783748 KB Output is correct
3 Correct 639 ms 783484 KB Output is correct
4 Correct 647 ms 783404 KB Output is correct
5 Correct 705 ms 783564 KB Output is correct
6 Correct 687 ms 783864 KB Output is correct
7 Correct 732 ms 784008 KB Output is correct
8 Correct 736 ms 784140 KB Output is correct
9 Correct 782 ms 784028 KB Output is correct
10 Correct 704 ms 783892 KB Output is correct
11 Correct 735 ms 783900 KB Output is correct
12 Correct 720 ms 784216 KB Output is correct
13 Correct 654 ms 783916 KB Output is correct
14 Correct 689 ms 783880 KB Output is correct
15 Correct 698 ms 783936 KB Output is correct
16 Correct 739 ms 784072 KB Output is correct
17 Correct 1385 ms 783888 KB Output is correct
18 Correct 2827 ms 784132 KB Output is correct
19 Correct 699 ms 783992 KB Output is correct
20 Correct 719 ms 783908 KB Output is correct
21 Execution timed out 3091 ms 784212 KB Time limit exceeded
22 Halted 0 ms 0 KB -