oj.uz

Submission #1101968

# Submission time Handle Problem Language Result Execution time Memory
1101968 2024-10-17T08:51:20 Z vjudge1 Museum (CEOI17_museum) C++17
100 / 100
 419 ms 140360 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 10000 + 2;
const int inf = 1 << 28;
int sz[N];
vector<pair<int, int>> g[N];
vector<int> dp[N][2];
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]; 
	}
	dp[u][0].resize(sz[u] + 1, inf);
	dp[u][1].resize(sz[u] + 1, 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';
	// cout << "Ei porjonto thik ache" << endl;
}

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 1104 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1104 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 1 ms 1104 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 3656 KB Output is correct
2 Correct 116 ms 3912 KB Output is correct
3 Correct 375 ms 136520 KB Output is correct
4 Correct 201 ms 44596 KB Output is correct
5 Correct 131 ms 12368 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 3656 KB Output is correct
2 Correct 116 ms 3912 KB Output is correct
3 Correct 375 ms 136520 KB Output is correct
4 Correct 201 ms 44596 KB Output is correct
5 Correct 131 ms 12368 KB Output is correct
6 Correct 113 ms 2928 KB Output is correct
7 Correct 282 ms 80456 KB Output is correct
8 Correct 419 ms 2296 KB Output is correct
9 Correct 346 ms 2376 KB Output is correct
10 Correct 142 ms 2888 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1104 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1104 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 1 ms 1104 KB Output is correct
6 Correct 113 ms 3656 KB Output is correct
7 Correct 116 ms 3912 KB Output is correct
8 Correct 375 ms 136520 KB Output is correct
9 Correct 201 ms 44596 KB Output is correct
10 Correct 131 ms 12368 KB Output is correct
11 Correct 113 ms 2928 KB Output is correct
12 Correct 282 ms 80456 KB Output is correct
13 Correct 419 ms 2296 KB Output is correct
14 Correct 346 ms 2376 KB Output is correct
15 Correct 142 ms 2888 KB Output is correct
16 Correct 113 ms 4168 KB Output is correct
17 Correct 115 ms 4160 KB Output is correct
18 Correct 237 ms 54600 KB Output is correct
19 Correct 353 ms 2396 KB Output is correct
20 Correct 124 ms 3228 KB Output is correct
21 Correct 259 ms 77384 KB Output is correct
22 Correct 119 ms 3868 KB Output is correct
23 Correct 331 ms 2376 KB Output is correct
24 Correct 125 ms 2916 KB Output is correct
25 Correct 373 ms 140360 KB Output is correct