Submission #1088878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088878		juicy	Museum (CEOI17_museum)	C++17	100 / 100	507 ms	784472 KiB

museum

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e4;

int n, k, x;
int a[N][N + 1], b[N][N + 1];
vector<array<int, 2>> g[N];

int dfs(int u, int p) {
  int x = 1;
  a[u][1] = b[u][1] = 0;
  for (auto [v, w] : g[u]) {
    if (v ^ p) {
      int y = dfs(v, u);
      for (int i = x; i; --i) {
        for (int j = y; j; --j) {
          a[u][i + j] = min(a[u][i + j], a[u][i] + a[v][j] + 2 * w);
          b[u][i + j] = min({b[u][i + j], a[u][i] + b[v][j] + w, b[u][i] + a[v][j] + 2 * w});
        }
      }
      x += y;
    }
  }
  return x;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k >> x; --x;
  for (int i = 1; i < n; ++i) {
    int u, v, c; cin >> u >> v >> c; --u, --v;
    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }  
  memset(a, 0x3f, sizeof(a));
  memset(b, 0x3f, sizeof(b));
  dfs(x, x);
  cout << b[x][k];
  return 0;
}

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