Submission #977965

#	Time	Username	Problem	Language	Result	Execution time	Memory
977965		Beerus13	Museum (CEOI17_museum)	C++14	100 / 100	433 ms	785020 KiB

museum

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1e4 + 5;
const int inf = 1e9;

bool minimize(auto &a, auto b) {
    if(a <= b) return true;
    a = b;
    return false;
}

int n, k, x, sz[N];
int dp[2][N][N];
// 0: don't return to starting point
vector<pii> g[N];

void dfs(int u, int p = 0) {
    sz[u] = 1;
    dp[0][u][0] = dp[0][u][1] = 0;
    dp[1][u][0] = dp[1][u][1] = 0;
    for(auto [v, w] : g[u]) if(v != p) {
        dfs(v, u);
        for(int i = sz[u]; i >= 0; --i) {
            for(int j = 0; j <= sz[v]; ++j) {
                minimize(dp[0][u][i + j], dp[1][u][i] + dp[0][v][j] + w);
                minimize(dp[0][u][i + j], dp[0][u][i] + dp[1][v][j] + 2 * w);
                minimize(dp[1][u][i + j], dp[1][u][i] + dp[1][v][j] + 2 * w);
            }
        }
        sz[u] += sz[v];
    }
}

void solve() {
    cin >> n >> k >> x;
    for(int i = 1, u, v, w; i < n; ++i) {
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    memset(dp, 0x3f, sizeof(dp));
    dfs(x);
    cout << dp[0][x][k] << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message (stderr)

museum.cpp:8:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool minimize(auto &a, auto b) {
      |               ^~~~
museum.cpp:8:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool minimize(auto &a, auto b) {
      |                        ^~~~
museum.cpp: In function 'void dfs(int, int)':
museum.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [v, w] : g[u]) if(v != p) {
      |              ^

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