Submission #1246507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246507		julia_08	Museum (CEOI17_museum)	C++20	100 / 100	568 ms	784884 KiB

museum

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

const int MAXN = 1e4 + 10;

int sub[MAXN];

int dp[MAXN][MAXN][2], min_dp[MAXN][MAXN];

vector<pair<int, int>> adj[MAXN];

int n, k, x;

void init(int v){

  sub[v] = 1;

  for(int i=0; i<=n; i++) dp[v][i][0] = dp[v][i][1] = 1e9;

  dp[v][0][0] = dp[v][1][0] = 0;
  dp[v][0][1] = dp[v][1][1] = 0;

}

void merge(int u, int w, int v){

  for(int i=sub[v]; i>=0; i--){
    for(int j=sub[u]; j>=0; j--){
      dp[v][i + j][1] = min(dp[v][i + j][1], dp[v][i][1] + dp[u][j][1] + 2 * w);
      dp[v][i + j][0] = min(dp[v][i + j][0], dp[v][i][0] + dp[u][j][1] + 2 * w);
      dp[v][i + j][0] = min(dp[v][i + j][0], dp[v][i][1] + dp[u][j][0] + w);
    }
  }

  sub[v] += sub[u];

}

void dfs(int v, int p){

  init(v);

  for(auto [u, w] : adj[v]){
    if(u != p){
      dfs(u, v);
      merge(u, w, v);
    }
  }

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k >> x;

  for(int i=1; i<n; i++){
    int a, b, c; cin >> a >> b >> c;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }

  dfs(x, x);

  cout << dp[x][k][0] << "\n";

  return 0;
}

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