Submission #1254716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254716		dbence	Museum (CEOI17_museum)	C++20	0 / 100	469 ms	786724 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;

struct Graph {
    int par[N];
    int cnt[N];
    int ans0[N][N];
    int ans1[N][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 cnt = 1;
    int cpy0[N] = {0};
    int cpy1[N] = {0};

    fill(g.ans0[u], g.ans0[u] + N, inf);
    fill(g.ans1[u], g.ans1[u] + N, inf);
    g.ans0[u][0] = 0;
    g.ans0[u][1] = 0;
    g.ans1[u][0] = 0;
    g.ans1[u][1] = 0;

    for (auto [v, w]: g.adj[u]) {
        if (g.par[u] == v) {
            continue;
        }
        calc(v);
        copy(g.ans0[u], g.ans0[u] + N, cpy0);
        copy(g.ans0[u], g.ans0[u] + N, cpy1);
        for (int i = 1; i <= g.cnt[v]; ++i) {
            for (int j = 1; j <= cnt; ++j) {
                g.ans1[u][i + j] = min(g.ans1[u][i + j], g.ans1[v][i] + cpy0[j] + w);
                g.ans1[u][i + j] = min(g.ans1[u][i + j], g.ans0[v][i] + cpy1[j] + w * 2);
                g.ans0[u][i + j] = min(g.ans0[u][i + j], g.ans0[v][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});
    }
    dfs(x);
    calc(x);
    cout << g.ans1[x][k] << "\n";
}

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