oj.uz

Submission #134483

# Submission time Handle Problem Language Result Execution time Memory
134483 2019-07-22T19:36:48 Z dragonslayerit Museum (CEOI17_museum) C++14
100 / 100
 401 ms 180656 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 2 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 5012 KB Output is correct
2 Correct 161 ms 5304 KB Output is correct
3 Correct 389 ms 180344 KB Output is correct
4 Correct 236 ms 63608 KB Output is correct
5 Correct 178 ms 17928 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 5012 KB Output is correct
2 Correct 161 ms 5304 KB Output is correct
3 Correct 389 ms 180344 KB Output is correct
4 Correct 236 ms 63608 KB Output is correct
5 Correct 178 ms 17928 KB Output is correct
6 Correct 161 ms 3804 KB Output is correct
7 Correct 299 ms 114804 KB Output is correct
8 Correct 401 ms 2592 KB Output is correct
9 Correct 315 ms 2808 KB Output is correct
10 Correct 182 ms 3812 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 2 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 160 ms 5012 KB Output is correct
7 Correct 161 ms 5304 KB Output is correct
8 Correct 389 ms 180344 KB Output is correct
9 Correct 236 ms 63608 KB Output is correct
10 Correct 178 ms 17928 KB Output is correct
11 Correct 161 ms 3804 KB Output is correct
12 Correct 299 ms 114804 KB Output is correct
13 Correct 401 ms 2592 KB Output is correct
14 Correct 315 ms 2808 KB Output is correct
15 Correct 182 ms 3812 KB Output is correct
16 Correct 162 ms 5840 KB Output is correct
17 Correct 160 ms 5496 KB Output is correct
18 Correct 256 ms 71272 KB Output is correct
19 Correct 332 ms 2616 KB Output is correct
20 Correct 169 ms 3960 KB Output is correct
21 Correct 288 ms 110968 KB Output is correct
22 Correct 160 ms 5368 KB Output is correct
23 Correct 329 ms 2712 KB Output is correct
24 Correct 169 ms 4180 KB Output is correct
25 Correct 395 ms 180656 KB Output is correct