Submission #1106068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106068		Zero_OP	Museum (CEOI17_museum)	C++14	100 / 100	189 ms	140920 KiB

museum

#include <bits/stdc++.h>

using namespace std;

template<typename T> bool minimize(T& a, const T& b){
    if(a > b) return a = b, true; return false;
}

#define sizeVec(v) (int)v.size()

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, K, X;
    cin >> N >> K >> X; --X;
    vector<vector<pair<int, int>>> adj(N);
    for(int i = 1; i < N; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }


    const int inf = 1e9;
    vector<int> sz(N);
    vector<vector<int>> f(N), g(N);

    function<void(int, int)> dfs = [&](int u, int p){
        sz[u] = 1;
        for(auto [v, w] : adj[u]) if(v != p){
            dfs(v, u);
            sz[u] += sz[v];
        }

        f[u].resize(sz[u] + 1, inf);
        g[u].resize(sz[u] + 1, inf);
        f[u][1] = 0; //at somewhere
        g[u][1] = 0; //at u

        int sumSize = 1;
        for(auto [v, w] : adj[u]) if(v != p){
            for(int i = sumSize; i >= 1; --i){
                for(int j = sz[v]; j >= 1; --j){
                    minimize(f[u][i + j], min(f[u][i] + g[v][j] + 2 * w, g[u][i] + f[v][j] + w));
                    minimize(g[u][i + j], g[u][i] + g[v][j] + 2 * w);
                }
            }

            sumSize += sz[v];
        }
    };

    dfs(X, -1);

    cout << min(f[X][K], g[X][K]) << '\n';

    return 0;
}

Compilation message (stderr)

museum.cpp: In function 'bool minimize(T&, const T&)':
museum.cpp:6:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    6 |     if(a > b) return a = b, true; return false;
      |     ^~
museum.cpp:6:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    6 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
museum.cpp: In lambda function:
museum.cpp:37:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |         for(auto [v, w] : adj[u]) if(v != p){
      |                  ^
museum.cpp:48:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         for(auto [v, w] : adj[u]) if(v != p){
      |                  ^

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