Submission #1274309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274309		beny	Museum (CEOI17_museum)	C++20	80 / 100	3127 ms	785108 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;
int dp[N][2][N];
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][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]);
            }
        }
    }
}

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 });
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dp[i][0][j] = dp[i][1][j] = 1e9;
        }
    }

    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:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d%d%d", &n, &k, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:53:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         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