Submission #1104420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104420		f0rizen	Museum (CEOI17_museum)	C++17	100 / 100	323 ms	172060 KiB

museum

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct Edge {
    int to, w;
};

vector<vector<Edge>> g;
vector<int> sz;
vector<vector<array<int, 2>>> dp;

void dfs(int v, int p = -1) {
    sz[v] = 1;
    for (auto [u, w] : g[v]) {
        if (u != p) {
            dfs(u, v);
            sz[v] += sz[u];
        }
    }
    dp[v].resize(2);
    for (int i = 0; i < 2; ++i) {
        dp[v][i][0] = inf;
        dp[v][i][0] = inf;
    }
    dp[v][1][0] = 0;
    dp[v][1][1] = 0;
    int cur = 1;
    for (auto [u, w] : g[v]) {
        if (u != p) {
            vector<array<int, 2>> dpp(cur + sz[u] + 1);
            for (int i = 0; i <= cur + sz[u]; ++i) {
                dpp[i][0] = inf;
                dpp[i][1] = inf;
            }
            for (int i = 0; i <= cur; ++i) {
                for (int j = 0; j <= sz[u]; ++j) {
                    if (j == 0) {
                        dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][0]);
                        dpp[i + j][1] = min(dpp[i + j][1], dp[v][i][1]);
                    } else {
                        dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][1] + dp[u][j][0] + w);
                        dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][0] + dp[u][j][1] + 2 * w);
                        dpp[i + j][1] = min(dpp[i + j][1], dp[v][i][1] + dp[u][j][1] + 2 * w);
                    }
                }
            }
            dp[v] = dpp;
            cur += sz[u];
        }
    }
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, k, x;
    cin >> n >> k >> x;
    --x;
    g.resize(n);
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    sz.resize(n);
    dp.resize(n);
    dfs(x);
    cout << dp[x][k][0] << "\n";
    return 0;
}

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