Submission #1274285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274285		beny	Museum (CEOI17_museum)	C++20	0 / 100	12 ms	1740 KiB

museum

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define ll long long
#define smid (nl + nr) / 2
#define lc id * 2
#define rc id * 2 + 1
#define migmig std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);std::cout.tie(NULL);
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const int N = 1e4 + 5;
vector<int> dp[N][2];
vector<pair<int, int>> adj[N];
int sz[N];
int n, k, x;

void dfs (int v, int pre = 0) {
    sz[v] = 1;
    for (auto [u, c] : adj[v]) {
        if (u == pre) continue;
        dfs(u, v);
        sz[v] += sz[u];
    }

    for (int i = 0; i <= min(sz[v], k); i++) {
        dp[v][0].push_back(1e9);
        dp[v][1].push_back(1e9);
    }
    dp[v][0][1] = 0;
    dp[v][1][1] = 0;

    for (auto [u, c] : adj[v]) {
        if (u == pre) continue;
        for (int j = min(k, sz[v]); j > 0; j--) {
            for (int l = min(k, sz[u]); l > 0; l--) {
                if (j >= l) dp[v][0][j] = min(dp[v][0][j], dp[u][0][l] + c + dp[v][1][j - l]);
                if (j >= l) dp[v][1][j] = min(dp[v][1][j], dp[u][1][l] + c + c + dp[v][1][j - l]);
            }
        }
    }


    for (auto [u, c] : adj[v]) {
        if (u == pre) continue;
        dp[u][0].clear();
        dp[u][1].clear();
        dp[u][0].shrink_to_fit();
        dp[u][1].shrink_to_fit();
    }
}

void solve() {
    cin >> n >> k >> x;
    for (int i = 1; i < n; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }

    dfs(x);

    cout << dp[x][0][k];
}

int main() {
    migmig;

    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
}

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