oj.uz

Submission #155711

# Submission time Handle Problem Language Result Execution time Memory
155711 2019-09-30T03:26:57 Z Fischer Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 784760 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 2;
struct Node {
	int v, w;
};
vector<Node> g[maxn];
int n, k, x;
int sz[maxn];
int memo[maxn][maxn][2];

void dfs(int x, int p) {
	sz[x] = 1;
	for (auto node : g[x]) {
		if (node.v == p) continue;
		dfs(node.v, x);
		sz[x] += sz[node.v];
	}
	memo[x][1][0] = memo[x][1][1] = 0; 
	for (auto node : g[x]) {
		if (node.v == p) continue;
		for (int i = min(sz[x], k); i >= 2; --i) {
			for (int j = min(sz[node.v], i-1); j >= 1; --j) {
				memo[x][i][1] = min(memo[x][i][1],
					min(
						memo[x][i-j][1] + memo[node.v][j][0] + (node.w<<1),
						memo[x][i-j][0] + memo[node.v][j][1] + node.w
					));
				memo[x][i][0] = min(memo[x][i][0], 
					memo[x][i-j][0] + memo[node.v][j][0] + (node.w<<1));
			}
		}
	}
}

int main() {
	cin >> n >> k >> x;
	for (int i = 1; i <= n-1; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	memset(memo, 63, sizeof memo);
	dfs(x, 0);
	cout << memo[x][k][1] << endl;
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 783672 KB Output is correct
2 Correct 647 ms 783740 KB Output is correct
3 Correct 648 ms 783748 KB Output is correct
4 Correct 672 ms 783604 KB Output is correct
5 Correct 647 ms 783616 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 784148 KB Output is correct
2 Correct 691 ms 784224 KB Output is correct
3 Correct 712 ms 784760 KB Output is correct
4 Correct 691 ms 784424 KB Output is correct
5 Correct 696 ms 784300 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 784148 KB Output is correct
2 Correct 691 ms 784224 KB Output is correct
3 Correct 712 ms 784760 KB Output is correct
4 Correct 691 ms 784424 KB Output is correct
5 Correct 696 ms 784300 KB Output is correct
6 Correct 693 ms 784312 KB Output is correct
7 Correct 727 ms 784632 KB Output is correct
8 Correct 673 ms 784404 KB Output is correct
9 Correct 665 ms 784276 KB Output is correct
10 Correct 667 ms 784200 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 783672 KB Output is correct
2 Correct 647 ms 783740 KB Output is correct
3 Correct 648 ms 783748 KB Output is correct
4 Correct 672 ms 783604 KB Output is correct
5 Correct 647 ms 783616 KB Output is correct
6 Correct 673 ms 784148 KB Output is correct
7 Correct 691 ms 784224 KB Output is correct
8 Correct 712 ms 784760 KB Output is correct
9 Correct 691 ms 784424 KB Output is correct
10 Correct 696 ms 784300 KB Output is correct
11 Correct 693 ms 784312 KB Output is correct
12 Correct 727 ms 784632 KB Output is correct
13 Correct 673 ms 784404 KB Output is correct
14 Correct 665 ms 784276 KB Output is correct
15 Correct 667 ms 784200 KB Output is correct
16 Correct 759 ms 784216 KB Output is correct
17 Correct 1478 ms 784412 KB Output is correct
18 Execution timed out 3085 ms 784376 KB Time limit exceeded
19 Halted 0 ms 0 KB -