Submission #444901

#	Time	Username	Problem	Language	Result	Execution time	Memory
444901		ivan_tudor	Museum (CEOI17_museum)	C++14	100 / 100	920 ms	785092 KiB

museum

#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
struct Edges{
  int x, c;
};
vector<Edges> gr[N];
int sz[N];
void dfs_prec(int nod, int dad){
  sz[nod] = 1;
  for(auto x:gr[nod])
  if(x.x!=dad){
    dfs_prec(x.x, nod);
    sz[nod] += sz[x.x];
  }
}
int dp[2][N][N];
void joindp(int dp1[], int sz1, int dp2[], int sz2, int dpans[], int val){
  for(int i = sz1; i >=0; i--){
    for(int j = sz2; j>=0; j--){
      dpans[i + j] = min(dpans[i + j], dp1[i] + dp2[j] + val);
    }
  }
}
void dfs(int nod, int dad){
  for(auto x:gr[nod]){
    if(x.x != dad){
      dfs(x.x, nod);
    }
  }
  dp[0][nod][0] = 0;
  dp[1][nod][0] = 0;
  dp[0][nod][1] = 0;
  dp[1][nod][1] = 0;
  int cursz = 1;
  for(auto x:gr[nod]){
    if(x.x == dad)
      continue;
    joindp(dp[1][nod], cursz, dp[0][x.x], sz[x.x], dp[1][nod], 2*x.c);
    joindp(dp[0][nod], cursz, dp[1][x.x], sz[x.x], dp[1][nod], x.c);
    joindp(dp[0][nod], cursz, dp[0][x.x], sz[x.x], dp[0][nod], 2*x.c);
    cursz+=sz[x.x];
  }

}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  for(int i = 0; i < 2; i++){
    for(int j = 0; j < N; j++){
      for(int k = 0; k < N; k++){
        dp[i][j][k] = INT_MAX;
      }
    }
  }
  int n, k, x;
  cin>>n>>k>>x;
  for(int i =1; i < n; i++){
    int a, b, c;
    cin>>a>>b>>c;
    gr[a].push_back({b, c});
    gr[b].push_back({a, c});
  }
  dfs_prec(x, 0);
  dfs(x, 0);
  cout<<dp[1][x][k];
  return 0;
}

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