oj.uz

Submission #135337

# Submission time Handle Problem Language Result Execution time Memory
135337 2019-07-24T03:51:11 Z dragonslayerit Chase (CEOI17_chase) C++14
0 / 100
 742 ms 135960 KB 
#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,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=1;i<=V;i++){
    setmax(up[i],up[i-1]+ss[node]-ps[parent]);
  }
  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];
  }
  long long ans=0;
  setmax(ans,dfs(0,N,std::vector<long long>(V+1))[V]);
  for(int i=0;i<N;i++){
    std::reverse(adj[i].begin(),adj[i].end());
  }
  setmax(ans,dfs(0,N,std::vector<long long>(V+1))[V]);
  printf("%lld\n",ans);
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Incorrect 4 ms 2680 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Incorrect 4 ms 2680 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 742 ms 135960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Incorrect 4 ms 2680 KB Output isn't correct
3 Halted 0 ms 0 KB -