oj.uz

Submission #155714

# Submission time Handle Problem Language Result Execution time Memory
155714 2019-09-30T03:50:06 Z Fischer Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 783992 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 i = head[x]; ~i; i = nxt[i]) {
		int v = to[i], w = value[i];
		if (v == p) continue;
		dfs(v, x);
		sz[x] += sz[v];
		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: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 636 ms 783564 KB Output is correct
2 Correct 645 ms 783452 KB Output is correct
3 Correct 674 ms 783500 KB Output is correct
4 Correct 659 ms 783484 KB Output is correct
5 Correct 669 ms 783504 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 783764 KB Output is correct
2 Correct 647 ms 783744 KB Output is correct
3 Correct 697 ms 783992 KB Output is correct
4 Correct 713 ms 783912 KB Output is correct
5 Correct 670 ms 783736 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 783764 KB Output is correct
2 Correct 647 ms 783744 KB Output is correct
3 Correct 697 ms 783992 KB Output is correct
4 Correct 713 ms 783912 KB Output is correct
5 Correct 670 ms 783736 KB Output is correct
6 Correct 642 ms 783656 KB Output is correct
7 Correct 689 ms 783956 KB Output is correct
8 Correct 649 ms 783712 KB Output is correct
9 Correct 646 ms 783992 KB Output is correct
10 Correct 687 ms 783836 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 783564 KB Output is correct
2 Correct 645 ms 783452 KB Output is correct
3 Correct 674 ms 783500 KB Output is correct
4 Correct 659 ms 783484 KB Output is correct
5 Correct 669 ms 783504 KB Output is correct
6 Correct 655 ms 783764 KB Output is correct
7 Correct 647 ms 783744 KB Output is correct
8 Correct 697 ms 783992 KB Output is correct
9 Correct 713 ms 783912 KB Output is correct
10 Correct 670 ms 783736 KB Output is correct
11 Correct 642 ms 783656 KB Output is correct
12 Correct 689 ms 783956 KB Output is correct
13 Correct 649 ms 783712 KB Output is correct
14 Correct 646 ms 783992 KB Output is correct
15 Correct 687 ms 783836 KB Output is correct
16 Correct 727 ms 783864 KB Output is correct
17 Correct 1303 ms 783820 KB Output is correct
18 Correct 2851 ms 783920 KB Output is correct
19 Correct 693 ms 783864 KB Output is correct
20 Correct 746 ms 783760 KB Output is correct
21 Execution timed out 3078 ms 783888 KB Time limit exceeded
22 Halted 0 ms 0 KB -