Submission #223909

#	Time	Username	Problem	Language	Result	Execution time	Memory
223909		Leonardo_Paes	Museum (CEOI17_museum)	C++17	100 / 100	818 ms	785272 KiB

museum

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

const int maxn = 1e4+10, inf = 0x3f3f3f3f;

typedef pair<int,int> pii;

int n, k, x, siz[maxn], dp[maxn][maxn][2];

vector<pii> grafo[maxn];

void dfs(int u, int p = 0){
    siz[u] = 1;

    for(auto v : grafo[u]){
        if(v.f == p) continue;

        dfs(v.f, u);

        siz[u] += siz[v.f];
    }
}

int solve(int u, int p = 0){
    int sizes = 1, d;

    for(auto v : grafo[u]){
        if(v.f == p) continue;

        solve(v.f, u);

        sizes += siz[v.f];

        d = v.s;

        for(int i=sizes; i>=2; i--){
            for(int j=max(0, i-sizes+siz[v.f]); j<=min(i, siz[v.f]); j++){
                dp[u][i][0] = min({dp[u][i][0], dp[u][i-j][0] + dp[v.f][j][1]
                + 2*d, dp[u][i-j][1] + dp[v.f][j][0] + d});
                dp[u][i][1] = min({dp[u][i][1], dp[u][i-j][1] + dp[v.f][j][1] + 2*d});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> n >> k >> x;

    for(int i=1; i<n; i++){
        int u, v, d;

        cin >> u >> v >> d;

        grafo[u].push_back({v, d});
        grafo[v].push_back({u, d});
    }

    dfs(x);

    for(int i=1; i<=n; i++){
        for(int j=2; j<=n; j++){
            dp[i][j][0] = dp[i][j][1] = inf;
        }
    }

    solve(x);

    cout << dp[x][k][0] << endl;

    return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int solve(int, int)':
museum.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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