제출 #1276686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276686		iustinmircea10	Museum (CEOI17_museum)	C++17	20 / 100	3103 ms	455156 KiB

museum

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)9e18;

int n, k, start_node;
vector<vector<pair<int,int>>> adj; // 0-based

// dp[u][s] = vector of candidate (time, dist) pairs for visiting s nodes in subtree(u)
// time = total walking time, dist = distance from u to last visited node in that candidate
vector<vector<vector<pair<ll,ll>>>> dp;

static inline void prune_vec(vector<pair<ll,ll>> &v) {
    if (v.empty()) return;
    sort(v.begin(), v.end(), [](const pair<ll,ll>&a, const pair<ll,ll>&b){
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    });
    // compress equal times, keep minimal dist
    vector<pair<ll,ll>> tmp;
    tmp.reserve(v.size());
    for (auto &p : v) {
        if (tmp.empty() || p.first != tmp.back().first) tmp.push_back(p);
        else if (p.second < tmp.back().second) tmp.back().second = p.second;
    }
    // keep non-dominated: times increasing, keep only pairs with strictly smaller dist than any kept before
    vector<pair<ll,ll>> kept;
    kept.reserve(tmp.size());
    ll best_dist = INF;
    for (auto &p : tmp) {
        if (p.second < best_dist) {
            kept.push_back(p);
            best_dist = p.second;
        }
    }
    v.swap(kept);
}

void dfs(int u, int p) {
    dp[u].clear();
    dp[u].resize(2);
    dp[u][0].push_back({0,0}); // visiting 0 nodes
    dp[u][1].push_back({0,0}); // visiting only u: time 0, dist 0

    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        dfs(v, u);

        int a_sz = (int)dp[u].size();
        int b_sz = (int)dp[v].size();
        int new_sz = a_sz + b_sz - 1;
        vector<vector<pair<ll,ll>>> newdp(new_sz);

        // copy old dp[u] (cases where we don't take anything from v)
        for (int i = 0; i < a_sz; ++i) {
            newdp[i].insert(newdp[i].end(), dp[u][i].begin(), dp[u][i].end());
        }

        // combine: i from u, j from v (both >= 1)
        for (int i = 1; i < a_sz; ++i) {
            for (int j = 1; j < b_sz; ++j) {
                int newk = i + j;
                // combine every candidate pair from dp[u][i] and dp[v][j]
                for (auto &A : dp[u][i]) {
                    for (auto &B : dp[v][j]) {
                        // u-first then v: must return from A's endpoint to u, go to v, do B (starting at v)
                        ll t1 = A.first + A.second + w + B.first;
                        ll d1 = B.second + w; // new endpoint distance from u
                        newdp[newk].push_back({t1, d1});

                        // v-first then u: go to v, do B, return to u, then do A
                        ll t2 = w + B.first + B.second + w + A.first;
                        ll d2 = A.second; // endpoint remains as in A
                        newdp[newk].push_back({t2, d2});
                    }
                }
            }
        }

        // prune each newdp[k] to keep only Pareto-optimal states
        for (int t = 0; t < new_sz; ++t) {
            prune_vec(newdp[t]);
        }

        dp[u].swap(newdp);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k >> start_node;
    --start_node; // convert to 0-based
    adj.assign(n, {});
    for (int i = 1; i < n; ++i) {
        int u,v,w; cin >> u >> v >> w; --u; --v;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    dp.assign(n, {});
    dfs(start_node, -1);

    if (k >= (int)dp[start_node].size()) {
        cout << "-1\n"; // or handle accordingly if impossible
        return 0;
    }
    // answer is minimal 'time' among candidates for dp[start][k]
    ll ans = INF;
    for (auto &p : dp[start_node][k]) ans = min(ans, p.first);
    cout << ans << "\n";
    return 0;
}

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