Submission #134483

#	Time	Username	Problem	Language	Result	Execution time	Memory
134483		dragonslayerit	Museum (CEOI17_museum)	C++14	100 / 100	401 ms	180656 KiB

museum

#include <cstdio>
#include <vector>
#include <algorithm>

const int INF=1e9+7;

std::vector<std::pair<int,int> > edges[10001];

std::vector<int> dp1[10001];
std::vector<int> dp2[10001];


void dfs(int node,int parent=-1,int plen=0){
  dp1[node].push_back(0);
  dp2[node].push_back(0);
  for(auto e:edges[node]){
    int child=e.first;
    if(child==parent) continue;
    dfs(child,node,e.second);
    {
      std::vector<int> upd(dp1[node].size()+dp1[child].size()-1,INF);
      for(int a=0;a<dp1[node].size();a++){
	for(int b=0;b<dp1[child].size();b++){
	  upd[a+b]=std::min(upd[a+b],dp1[node][a]+dp2[child][b]);
	  upd[a+b]=std::min(upd[a+b],dp2[node][a]+dp1[child][b]);
	}
      }
      std::swap(upd,dp2[node]);
    }
    {
      std::vector<int> upd(dp1[node].size()+dp1[child].size()-1,INF);
      for(int a=0;a<dp1[node].size();a++){
	for(int b=0;b<dp1[child].size();b++){
	  upd[a+b]=std::min(upd[a+b],dp1[node][a]+dp1[child][b]);
	}
      }
      std::swap(upd,dp1[node]);
    }
  }
  for(int& x:dp1[node]){
    x+=plen*2;
  }
  for(int& x:dp2[node]){
    x+=plen;
  }
  dp1[node].insert(dp1[node].begin(),0);
  dp2[node].insert(dp2[node].begin(),0);
  /*
  for(int i=0;i<dp1[node].size();i++){
    printf("%d: %d\n",node,dp1[node][i]);
  }
  */
}

int main(){
  int N,K,X;
  scanf("%d %d %d",&N,&K,&X);
  X--;
  for(int i=0;i<N-1;i++){
    int A,B,C;
    scanf("%d %d %d",&A,&B,&C);
    A--,B--;
    edges[A].push_back({B,C});
    edges[B].push_back({A,C});
  }
  dfs(X);
  printf("%d\n",dp2[X][K]);
}

Compilation message (stderr)

museum.cpp: In function 'void dfs(int, int, int)':
museum.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int a=0;a<dp1[node].size();a++){
                   ~^~~~~~~~~~~~~~~~~
museum.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int b=0;b<dp1[child].size();b++){
              ~^~~~~~~~~~~~~~~~~~
museum.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int a=0;a<dp1[node].size();a++){
                   ~^~~~~~~~~~~~~~~~~
museum.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int b=0;b<dp1[child].size();b++){
              ~^~~~~~~~~~~~~~~~~~
museum.cpp: In function 'int main()':
museum.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&N,&K,&X);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
museum.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&A,&B,&C);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~

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