Submission #1022735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022735		anarch_y	Museum (CEOI17_museum)	C++17	100 / 100	503 ms	421812 KiB

museum

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define int long long

vector<int> combine(vector<int> a, vector<int> b, int x){
    vector<int> c(sz(a)+sz(b)-1, 1e18);
    for(int i=0; i<sz(a); i++){
        for(int j=0; j<sz(b); j++){
            c[i+j] = min(c[i+j], a[i]+b[j]+x);
        }
    }
    return c;
}

vector<int> find_min(vector<int> a, vector<int> b){
    vector<int> c(sz(a));
    for(int i=0; i<sz(a); i++){
        c[i] = min(a[i], b[i]);
    }
    return c;
}

const int maxn = 10001;
vector<pair<int, int>> adj[maxn];
vector<int> dp[maxn][2];

void dfs(int s, int p){
    dp[s][0] = {(int)1e18, 0};
    dp[s][1] = {(int)1e18, 0};
    for(auto [u, w]: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        dp[u][0][0] = -2*w; dp[u][1][0] = -w;
        auto c = combine(dp[s][0], dp[u][0], 2*w);
        auto a = combine(dp[s][1], dp[u][0], 2*w);
        auto b = combine(dp[s][0], dp[u][1], w);
        dp[s][0] = c;
        dp[s][1] = find_min(a, b);
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k, x; cin >> n >> k >> x;
    for(int i=0; i<n-1; i++){
        int a, b, w; cin >> a >> b >> w;
        adj[a].pb({b, w}); adj[b].pb({a, w});
    }
    dfs(x, 0);
    cout << dp[x][1][k];
}

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