Submission #135334

#	Time	Username	Problem	Language	Result	Execution time	Memory
135334		dragonslayerit	Chase (CEOI17_chase)	C++14	40 / 100	4021 ms	53400 KiB

chase

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

void setmax(long long& x,long long y){
  x=std::max(x,y);
}

int ps[100005];
long long ss[100005];
std::vector<int> adj[100005];
int V;

std::vector<long long> dfs(int node,int parent=-1){
  std::vector<long long> res(V+1,0);
  for(int i=1;i<=V;i++){
    res[i]=ss[node];
  }
  for(int child:adj[node]){
    if(child==parent) continue;
    auto partial=dfs(child,node);
    for(int i=0;i<=V;i++){
      setmax(res[i],partial[i]);
      if(i) setmax(res[i],partial[i-1]+ss[node]-ps[child]);
    }
  }
  return res;
}

int main(){
  int N;
  scanf("%d %d",&N,&V);
  for(int i=0;i<N;i++){
    scanf("%d",&ps[i]);
  }
  for(int i=0;i<N-1;i++){
    int A,B;
    scanf("%d %d",&A,&B);
    A--,B--;
    adj[A].push_back(B);
    adj[B].push_back(A);
    ss[A]+=ps[B];
    ss[B]+=ps[A];
  }
  long long ans=0;
  for(int i=0;i<N;i++){
    setmax(ans,dfs(i)[V]);
  }
  printf("%lld\n",ans);
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&V);
   ~~~~~^~~~~~~~~~~~~~~
chase.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&ps[i]);
     ~~~~~^~~~~~~~~~~~~
chase.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&A,&B);
     ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30