Submission #1115122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115122		_Sherbiny	Museum (CEOI17_museum)	C++17	100 / 100	343 ms	289748 KiB

museum

// Author: _Sherbiny

#include "bits/stdc++.h"
using namespace std;

#ifdef DBG
#include "./debug.h"
#else
#define dbg(...)
#endif

typedef long long ll;
#define endl '\n'
#define int ll
//==================//
const int N = 1e4 + 2;
int n, k;

array<int, 2> oo;
vector<array<int, 2>> dp[N];
vector<vector<pair<int, int>>> adj;

void merge(int u, int v, int c) {
    auto ret = dp[u];
    ret.resize(dp[u].size() + dp[v].size() - 1, oo);

    for(int i = 1; i < dp[u].size(); ++i)
        for(int j = 1; j < dp[v].size(); ++j) {
            ret[i + j][0] = min(ret[i + j][0], dp[u][i][0] + dp[v][j][0] + c * 2);
            ret[i + j][1] = min({ret[i + j][1], dp[u][i][1] + dp[v][j][0] + c * 2, dp[u][i][0] + dp[v][j][1] + c});
        }

    swap(ret, dp[u]);
}

void go(int u, int p = 0) {
    for(auto[v, c]: adj[u])
        if(v != p) go(v, u);

    dp[u].assign(2, {});
    for(auto &[v, c]: adj[u])
        if(v != p) merge(u, v, c);
}

void magic() {
    cin >> n >> k;
    int x; cin >> x;
    oo.fill(2e18);

    adj.assign(n + 1, {});
    for (int i = 0; i < n - 1; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    go(x);
    cout << dp[x][k][1];
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--) magic();
}

Compilation message (stderr)

museum.cpp: In function 'void merge(ll, ll, ll)':
museum.cpp:27:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 1; i < dp[u].size(); ++i)
      |                    ~~^~~~~~~~~~~~~~
museum.cpp:28:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int j = 1; j < dp[v].size(); ++j) {
      |                        ~~^~~~~~~~~~~~~~

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