Submission #161451

#	Time	Username	Problem	Language	Result	Execution time	Memory
161451		Minnakhmetov	Museum (CEOI17_museum)	C++14	100 / 100	939 ms	785264 KiB

museum

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

struct E {
    int to, w;
};

const int N = 1e4 + 5, K = N, INF = 1e9;
vector<E> g[N];
int dp[N][K][2], sz[N];
int n, k, x;

void upd(int &x, int y) {
    x = min(x, y);
}

void dive(int node, int anc) {
    sz[node] = 1;
    for (E e : g[node]) {
        if (e.to != anc) {
            dive(e.to, node);
            sz[node] += sz[e.to];
        }
    }
}

void dfs(int node, int h, int anc) {
    dp[node][1][0] = dp[node][1][1] = 0;

    int sum = 1;
    for (E e : g[node]) {
        if (e.to != anc) {
            dfs(e.to, h + 1, node);

            for (int x = min(sum, k - h); x > 0; x--) {
                for (int y = 1; y <= min(sz[e.to], k - h - x); y++) {
                    upd(dp[node][x + y][0], dp[node][x][0] + dp[e.to][y][1] + e.w * 2);
                    upd(dp[node][x + y][0], dp[node][x][1] + dp[e.to][y][0] + e.w);
                    upd(dp[node][x + y][1], dp[node][x][1] + dp[e.to][y][1] + e.w * 2);
                }
            }
            sum += sz[e.to];
        }
    }
}

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

    cin >> n >> k >> x;
    x--;

    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K; j++) {
            for (int k = 0; k < 2; k++) {
                dp[i][j][k] = INF;
            }
        }
    }

    dive(x, -1);
    dfs(x, 0, -1);

    cout << dp[x][k][0];
 
    return 0;
}

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