Submission #135342

#	Time	Username	Problem	Language	Result	Execution time	Memory
135342		dragonslayerit	Chase (CEOI17_chase)	C++14	100 / 100	689 ms	139148 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;

long long ans=0;

std::vector<long long> dfs(int node,int parent,std::vector<long long> up){
  std::vector<long long> res(V+1);
  for(int i=1;i<=V;i++){
    res[i]=ss[node];
  }
  for(int i=V;i>0;i--){
    setmax(up[i],up[i-1]+ss[node]-ps[parent]);
  }
  setmax(ans,up[V]);
  for(int child:adj[node]){
    if(child==parent) continue;
    std::vector<long long> tmp(V+1);
    for(int i=0;i<=V;i++){
      tmp[i]=std::max(res[i],up[i]);
    }
    auto partial=dfs(child,node,tmp);
    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];
  }
  dfs(0,N,std::vector<long long>(V+1));
  for(int i=0;i<N;i++){
    std::reverse(adj[i].begin(),adj[i].end());
  }
  dfs(0,N,std::vector<long long>(V+1));
  printf("%lld\n",ans);
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:42: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:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&ps[i]);
     ~~~~~^~~~~~~~~~~~~
chase.cpp:48: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: 30 / 30
• Subtask 4: 30 / 30