Submission #1084681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084681		BF001	Museum (CEOI17_museum)	C++17	100 / 100	1883 ms	784512 KiB

museum

#include<bits/stdc++.h>
using namespace std;
 
#define N 10002
#define oo 1e9
#define fi first 
#define se second

typedef pair<int, int> ii;

int dp[2][N][N], n, root, k, siz[N];
vector<ii> adj[N];
 
void dfs(int u, int p){
    siz[u] = 1;
    dp[1][1][u] = dp[0][1][u] = dp[0][0][u] = dp[1][0][u] = 0;
    for (auto x : adj[u]){
        int v = x.fi, w = x.se;
        if (v == p) continue;
        dfs(v, u);
        for (int i = siz[u]; i >= 1; i--){
            for (int j = 1; j <= siz[v]; j++){
                dp[0][i + j][u] = min(dp[0][i + j][u], dp[1][i][u] + dp[0][j][v] + w);
                dp[0][i + j][u] = min(dp[0][i + j][u], dp[0][i][u] + dp[1][j][v] + 2 * w);
                dp[1][i + j][u] = min(dp[1][i + j][u], dp[1][i][u] + dp[1][j][v] + w * 2);
            }
        }
        siz[u] += siz[v];
    }

}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> k >> root;
    for (int i = 1; i <= n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    } 

    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= n; j++){
            dp[0][j][i] = dp[1][j][i] = oo;
        }
    }   
    
    dfs(root, 0);
    cout << dp[0][k][root];

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20