# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1104418 |
2024-10-23T17:24:20 Z |
f0rizen |
Museum (CEOI17_museum) |
C++17 |
|
165 ms |
15284 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;
template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
struct Edge {
int to, w;
};
vector<vector<Edge>> g;
vector<int> sz;
vector<vector<vector<int>>> dp;
void dfs(int v, int p = -1) {
sz[v] = 1;
for (auto [u, w] : g[v]) {
if (u != p) {
dfs(u, v);
sz[v] += sz[u];
}
}
dp[v].resize(2, vector<int>(2, inf));
dp[v][1][0] = 0;
dp[v][1][1] = 0;
int cur = 1;
for (auto [u, w] : g[v]) {
if (u != p) {
vector<vector<int>> dpp(cur + sz[u] + 1, vector<int>(2, inf));
for (int i = 0; i <= cur; ++i) {
for (int j = 0; j <= sz[u]; ++j) {
if (j == 0) {
dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][0]);
dpp[i + j][1] = min(dpp[i + j][1], dp[v][i][1]);
} else {
dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][1] + dp[u][j][0] + w);
dpp[i + j][1] = min(dpp[i + j][1], dp[v][i][1] + dp[u][j][1] + 2 * w);
}
}
}
dp[v] = dpp;
cur += sz[u];
}
}
}
int32_t main() {
#ifdef LOCAL
freopen("/tmp/input.txt", "r", stdin);
#else
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int n, k, x;
cin >> n >> k >> x;
--x;
g.resize(n);
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
sz.resize(n);
dp.resize(n);
dfs(x);
cout << dp[x][k][0] << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
165 ms |
15284 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
165 ms |
15284 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |