Submission #1254718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254718		dbence	Museum (CEOI17_museum)	C++20	100 / 100	390 ms	328280 KiB

museum

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (x).size()
#define lsb(x) (x) & (-x)
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

template <typename T>
void print(T t) {
    cout << t << "\n";
}

template <typename T, typename... Args>
void print(T t, Args ...args) {
    cout << t << " ";
    print(args...);
}

const int N = 10001;
const int inf = 1 << 29;
int n, k, x, cpy0[N], cpy1[N];

struct Graph {
    int par[N];
    int cnt[N];
    vector <pii> adj[N];
} g;

int dfs(int u) {
    g.cnt[u] = 1;
    for (auto [v, w]: g.adj[u]) {
        if (g.par[u] == v) {
            continue;
        }
        g.par[v] = u;
        g.cnt[u] += dfs(v);
    }
    return g.cnt[u];
}

void calc(int u, int ans0[N], int ans1[N]) {
    int cnt = 1;
    fill(ans0, ans0 + N, inf);
    fill(ans1, ans1 + N, inf);
    ans0[0] = ans0[1] = ans1[0] = ans1[1] = 0;

    for (auto [v, w]: g.adj[u]) {
        if (g.par[u] == v) {
            continue;
        }
        int ansv0[N], ansv1[N];
        calc(v, ansv0, ansv1);

        copy(ans0, ans0 + N, cpy0);
        copy(ans1, ans1 + N, cpy1);
        for (int i = 1; i <= g.cnt[v]; ++i) {
            for (int j = 1; j <= cnt; ++j) {
                ans1[i + j] = min(ans1[i + j], ansv1[i] + cpy0[j] + w);
                ans1[i + j] = min(ans1[i + j], ansv0[i] + cpy1[j] + w * 2);
                ans0[i + j] = min(ans0[i + j], ansv0[i] + cpy0[j] + w * 2);
            }   
        }
        cnt += g.cnt[v];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> x;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g.adj[u].pb({v, w});
        g.adj[v].pb({u, w});
    }
    int ans0[N], ans1[N];

    dfs(x);
    calc(x, ans0, ans1);
    cout << ans1[k] << "\n";
}

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