Submission #1274299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274299		beny	Museum (CEOI17_museum)	C++20	80 / 100	3092 ms	2160 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;

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#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];
    }

    dp[v][0].assign(min(sz[v], k) + 1, 1e9);
    dp[v][1].assign(min(sz[v], k) + 1, 1e9);
    dp[v][0][0] = 0;
    dp[v][0][1] = 0;
    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][0][j] = min(dp[v][0][j], dp[u][1][l] + c + c + dp[v][0][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() {
    scanf("%d%d%d", &n, &k, &x);
    for (int i = 1; i < n; i++) {
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }

    dfs(x);

    printf("%d", dp[x][0][k]);
}

int main() {
    migmig;

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

Compilation message (stderr)

museum.cpp: In function 'void solve()':
museum.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d%d%d", &n, &k, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:64:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         int a, b, c; scanf("%d%d%d", &a, &b, &c);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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