oj.uz

Submission #155716

# Submission time Handle Problem Language Result Execution time Memory
155716 2019-09-30T04:03:19 Z Fischer Museum (CEOI17_museum) C++11
100 / 100
 886 ms 784396 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 >= max(1, 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 656 ms 783468 KB Output is correct
2 Correct 641 ms 783516 KB Output is correct
3 Correct 639 ms 783608 KB Output is correct
4 Correct 636 ms 783408 KB Output is correct
5 Correct 637 ms 783452 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 783796 KB Output is correct
2 Correct 648 ms 783752 KB Output is correct
3 Correct 651 ms 784024 KB Output is correct
4 Correct 651 ms 783992 KB Output is correct
5 Correct 644 ms 783736 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 783796 KB Output is correct
2 Correct 648 ms 783752 KB Output is correct
3 Correct 651 ms 784024 KB Output is correct
4 Correct 651 ms 783992 KB Output is correct
5 Correct 644 ms 783736 KB Output is correct
6 Correct 649 ms 783676 KB Output is correct
7 Correct 650 ms 784060 KB Output is correct
8 Correct 648 ms 783864 KB Output is correct
9 Correct 675 ms 783784 KB Output is correct
10 Correct 696 ms 783768 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 783468 KB Output is correct
2 Correct 641 ms 783516 KB Output is correct
3 Correct 639 ms 783608 KB Output is correct
4 Correct 636 ms 783408 KB Output is correct
5 Correct 637 ms 783452 KB Output is correct
6 Correct 649 ms 783796 KB Output is correct
7 Correct 648 ms 783752 KB Output is correct
8 Correct 651 ms 784024 KB Output is correct
9 Correct 651 ms 783992 KB Output is correct
10 Correct 644 ms 783736 KB Output is correct
11 Correct 649 ms 783676 KB Output is correct
12 Correct 650 ms 784060 KB Output is correct
13 Correct 648 ms 783864 KB Output is correct
14 Correct 675 ms 783784 KB Output is correct
15 Correct 696 ms 783768 KB Output is correct
16 Correct 677 ms 783860 KB Output is correct
17 Correct 777 ms 783908 KB Output is correct
18 Correct 718 ms 783992 KB Output is correct
19 Correct 694 ms 783752 KB Output is correct
20 Correct 671 ms 783704 KB Output is correct
21 Correct 813 ms 784008 KB Output is correct
22 Correct 849 ms 783988 KB Output is correct
23 Correct 886 ms 783944 KB Output is correct
24 Correct 772 ms 783964 KB Output is correct
25 Correct 840 ms 784396 KB Output is correct