Submission #1153455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153455		spycoderyt	Museum (CEOI17_museum)	C++20	100 / 100	515 ms	785144 KiB

museum

// start 5:17
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 10005;
int sz[N];
vector<pair<int,int> > A[N];
int dp[2][N][N];
int n,k,x,a,b,c;
void dfs(int u,int par = -1) {
    dp[1][u][1] = dp[0][u][1] = 0;
    sz[u]=1;
    for(auto [nxt,w] : A[u]) if(nxt!=par){
        dfs(nxt,u);
        for(int i = min(k,sz[u] + sz[nxt]);i>=2;i--) {
            for(int j = min(i-1,sz[nxt]);j>=max(1,i-sz[u]);j--){
                dp[1][u][i] = min({
                    dp[1][u][i],
                    dp[0][u][i-j] + dp[1][nxt][j] + w,
                    dp[1][u][i-j] + dp[0][nxt][j] + 2 * w
                });
                dp[0][u][i] = min({
                    dp[0][u][i],
                    dp[0][u][i-j] + dp[0][nxt][j] + 2 * w
                });
            }
        }
        sz[u] += sz[nxt];
    }
}
int main() {
    cin>>n>>k>>x;
    for(int i = 0;i<n-1;i++) {
        cin>>a>>b>>c;
        A[a].push_back({b,c});
        A[b].push_back({a,c});
    }
    for(int i = 0;i<N;i++) for(int j = 0;j<N;j++) dp[0][i][j] = dp[1][i][j] = 1e9;
    dfs(x);
    cout<<dp[1][x][k];
}

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