Submission #533625

#	Time	Username	Problem	Language	Result	Execution time	Memory
533625		zxcvbnm	Museum (CEOI17_museum)	C++14	100 / 100	693 ms	784712 KiB

museum

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int nax = 10005;
constexpr int INF = 1e9 + 5;
int dp[nax][nax][2];
int sz[nax];
vector<pair<int, int>> adj[nax];

void self_min(int& me, int other) {
    me = min(me, other);
}

void dfs(int v, int p) {
    dp[v][1][0] = dp[v][1][1] = 0;
    sz[v] = 1;

    for(auto& child : adj[v]) {
        int u = child.first, w = child.second;
        if (u == p) continue;
        dfs(u, v);

        for(int i = sz[v]; i >= 0; i--) {
            for(int j = sz[u]; j >= 0; j--) {
                self_min(dp[v][i+j][0], dp[v][i][0]+dp[u][j][0]+2*w);
                self_min(dp[v][i+j][1], dp[v][i][1]+dp[u][j][0]+2*w);
                self_min(dp[v][i+j][1], dp[v][i][0]+dp[u][j][1]+w);
            }
        }
        sz[v] += sz[u];
    }

//    cout << v << " " << sz[v] << ": \n";
//    for(int i = 0; i <= sz[v]; i++) {
//        cout << i << ": " << dp[v][i][0] << " " << dp[v][i][1] << "\n";
//    }
//    cout << "--\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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].push_back({b, w});
        adj[b].push_back({a, w});
    }

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

    dfs(x, -1);
    cout << dp[x][k][1] << "\n";
    return 0;
}
/*

11 8 3
1 3 3
3 2 5
6 4 5
1 11 3
9 1 2
9 10 2
3 7 10
6 7 1
7 8 1
7 5 1


*/

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