Submission #1291461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291461		phucle	Museum (CEOI17_museum)	C++20	100 / 100	184 ms	2880 KiB

museum

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

using ll = long long;
const ll INF = (ll)4e18;

int n, K, X;
vector<pair<int,int>> g[100005];
int sz[100005];

struct NodeDP {
    vector<ll> f0, f1;
};

NodeDP dfs(int u, int p) {
    sz[u] = 1;

    NodeDP cur;
    cur.f0.assign(2, INF);
    cur.f1.assign(2, INF);
    cur.f0[1] = cur.f1[1] = 0;
    int curSZ = 1;

    for (auto [v, w] : g[u]) if (v != p) {
        NodeDP ch = dfs(v, u);
        int vsz = min(sz[v], K);
        int newSZ = min(K, curSZ + vsz);

        vector<ll> nf0(newSZ + 1, INF), nf1(newSZ + 1, INF);

        for (int i = 1; i <= curSZ; ++i) {
            if (cur.f0[i] >= INF && cur.f1[i] >= INF) continue;
            for (int j = 1; j <= vsz && i + j <= newSZ; ++j) {
                if (ch.f0[j] < INF) {
                    nf0[i + j] = min(nf0[i + j], cur.f1[i] + ch.f0[j] + w);
                }
                if (ch.f1[j] < INF) {
                    nf0[i + j] = min(nf0[i + j], cur.f0[i] + ch.f1[j] + 2LL*w);
                    nf1[i + j] = min(nf1[i + j], cur.f1[i] + ch.f1[j] + 2LL*w);
                }
            }
        }

        for (int i = 1; i <= curSZ; ++i) {
            nf0[i] = min(nf0[i], cur.f0[i]);
            nf1[i] = min(nf1[i], cur.f1[i]);
        }

        cur.f0.swap(nf0);
        cur.f1.swap(nf1);
        curSZ = newSZ;
        sz[u] += sz[v];
    }

    int need = min(sz[u], K);
    if ((int)cur.f0.size() > need + 1) cur.f0.resize(need + 1, INF);
    if ((int)cur.f1.size() > need + 1) cur.f1.resize(need + 1, INF);
    return cur;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> K >> X;
    for (int i=1;i<n;++i){
        int u,v,w; cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }

    NodeDP root = dfs(X, -1);
    cout << root.f0[K] << "\n";
    return 0;
}

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