Submission #1276683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276683		behrad	Museum (CEOI17_museum)	C++17	100 / 100	283 ms	138916 KiB

museum

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 1e4+4, mod = 1e9 + 7, inf = 2e14, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, K, X, sz[maxn];
vector<pii> g[maxn];

inline void mins(ll& a, ll b) { a = min(a, b); }

void dfs(int v, int p, vector<ll>& dp, vector<ll>& pd) {
  sz[v] = 1;
  dp.assign(sz[v] + 1, 0);
  pd.assign(sz[v] + 1, 0);

  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    vector<ll> dpu, pdu;
    dfs(u, v, dpu, pdu);

    vector<ll> tmp1, tmp2;
    tmp1.assign(min<int>(K + 1, dp.size() + dpu.size() + 1), inf);
    tmp2.assign(min<int>(K + 1, pd.size() + pdu.size() + 1), inf);

    for (int i = 0 ; i <= min(sz[v], K) ; i ++) {
      mins(tmp1[i], dp[i]);
      mins(tmp2[i], pd[i]);
      for (int j = 1 ; j <= min(sz[u], K) ; j ++) {
        if (i + j <= K) {
          mins(tmp1[i + j], dp[i] + dpu[j] + 2 * w);
          mins(tmp2[i + j], dp[i] + pdu[j] + w);
          mins(tmp2[i + j], dpu[j] + 2 * w + pd[i]);
        }
      }
    }
    
    sz[v] += sz[u];
    dp.swap(tmp1);
    pd.swap(tmp2);
    dp.resize(K + 1);
    pd.resize(K + 1);
  }
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n >> K >> X;
  for (int i = 1 , u, v,  w ; i < n ; i ++) {
    cin >> u >> v >> w;
    g[u].pb({v, w});
    g[v].pb({u, w});
  }

  vector<ll> dp, pd;
  dfs(X, 0, dp, pd);
  cout << pd[K] << nl;
}

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