oj.uz

Submission #1101946

# Submission time Handle Problem Language Result Execution time Memory
1101946 2024-10-17T08:32:11 Z vjudge1 Museum (CEOI17_museum) C++17
100 / 100
 549 ms 783692 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 10000 + 2;
const int inf = 1 << 28;
int sz[N];
int dp[N][2][N];
vector<pair<int, int>> g[N];
void calc_dp(int u, int p) {
	sz[u] = 1;
	for (auto &[v, c]: g[u]) {
		if (v == p) continue;
		calc_dp(v, u);
		sz[u] += sz[v]; 
	}
	for (int i = 0; i <= sz[u]; i++) dp[u][0][i] = dp[u][1][i] = inf;
	int len = 1;
	dp[u][0][0] = dp[u][1][0] = 0;
	dp[u][0][1] = dp[u][1][1] = 0;
	for (auto &[v, c]: g[u]) {
		if (v == p) continue;
		len += sz[v];
		for (int i = len; i >= 0; i--) {
			for (int j = max(0, i - (len - sz[v])); j <= min(i, sz[v]); j++) {
				dp[u][0][i] = min(dp[u][0][i], dp[u][1][i - j] + dp[v][0][j] + c);
				dp[u][0][i] = min(dp[u][0][i], dp[u][0][i - j] + dp[v][1][j] + c + c);
				dp[u][1][i] = min(dp[u][1][i], dp[u][1][i - j] + dp[v][1][j] + c + c);
			}
		}
	}
}
void solve() {
	int n, k, x;
	cin >> n >> k >> x;
	for (int i = 2; i <= n; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		g[u].push_back({v, c});
		g[v].push_back({u, c});
	}
	calc_dp(x, 0);
	cout << dp[x][0][k] << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    solve();
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 782984 KB Output is correct
2 Correct 227 ms 782936 KB Output is correct
3 Correct 374 ms 783376 KB Output is correct
4 Correct 268 ms 783436 KB Output is correct
5 Correct 236 ms 782924 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 782984 KB Output is correct
2 Correct 227 ms 782936 KB Output is correct
3 Correct 374 ms 783376 KB Output is correct
4 Correct 268 ms 783436 KB Output is correct
5 Correct 236 ms 782924 KB Output is correct
6 Correct 255 ms 783024 KB Output is correct
7 Correct 307 ms 783300 KB Output is correct
8 Correct 549 ms 783088 KB Output is correct
9 Correct 463 ms 783164 KB Output is correct
10 Correct 260 ms 783180 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 254 ms 782984 KB Output is correct
7 Correct 227 ms 782936 KB Output is correct
8 Correct 374 ms 783376 KB Output is correct
9 Correct 268 ms 783436 KB Output is correct
10 Correct 236 ms 782924 KB Output is correct
11 Correct 255 ms 783024 KB Output is correct
12 Correct 307 ms 783300 KB Output is correct
13 Correct 549 ms 783088 KB Output is correct
14 Correct 463 ms 783164 KB Output is correct
15 Correct 260 ms 783180 KB Output is correct
16 Correct 230 ms 782944 KB Output is correct
17 Correct 249 ms 782944 KB Output is correct
18 Correct 299 ms 783308 KB Output is correct
19 Correct 460 ms 782924 KB Output is correct
20 Correct 245 ms 783180 KB Output is correct
21 Correct 302 ms 783356 KB Output is correct
22 Correct 229 ms 783148 KB Output is correct
23 Correct 474 ms 782932 KB Output is correct
24 Correct 235 ms 783180 KB Output is correct
25 Correct 380 ms 783692 KB Output is correct