Submission #1248035

#TimeUsernameProblemLanguageResultExecution timeMemory
1248035uakkesMuseum (CEOI17_museum)C++20
100 / 100
258 ms140684 KiB
// // All truth are easy to understand once they are discovered. // The point is to discover them // #include <bits/stdc++.h> using namespace std; const int N = 1e4 + 1; vector<pair<int, int>> g[N]; vector<int> dp[N][2]; int sz[N], ndp[N + N][2]; // 0 - went backwards // 1 - did not went backwards void dfs(int v, int p) { sz[v] = 1; for (auto [u, c] : g[v]) { if (u == p) continue; dfs(u, v); sz[v] += sz[u]; } dp[v][0].resize(sz[v] + 1, 1e9); dp[v][1].resize(sz[v] + 1, 1e9); dp[v][0][1] = 0; dp[v][1][1] = 0; for (auto [u, c] : g[v]) { if (u == p) continue; for (int i = 0; i <= sz[v] + sz[u]; i++) { ndp[i][0] = ndp[i][1] = 1e9; } for (int i = 1; i <= sz[v]; i++) { if (dp[v][0][i] == 1e9) break; for (int j = 1; j <= sz[u]; j++) { ndp[i + j][0] = min(ndp[i + j][0], dp[v][0][i] + dp[u][0][j] + c * 2); ndp[i + j][1] = min(ndp[i + j][1], dp[v][1][i] + dp[u][0][j] + c * 2); ndp[i + j][1] = min(ndp[i + j][1], dp[v][0][i] + dp[u][1][j] + c); } } for (int i = 0; i <= sz[v]; i++) { dp[v][0][i] = min(dp[v][0][i], ndp[i][0]); dp[v][1][i] = min(dp[v][1][i], ndp[i][1]); } } } void solve(){ int n, k, x; cin >> n >> k >> x; for (int i = 1, c, u, v; i < n; i++) { cin >> u >> v >> c; g[u].emplace_back(v, c); g[v].emplace_back(u, c); } dfs(x, -1); cout << dp[x][1][k]; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; // cin >> tt; while (tt--) { solve(); cout << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...