oj.uz

Submission #135332

# Submission time Handle Problem Language Result Execution time Memory
135332 2019-07-24T03:34:36 Z dragonslayerit Chase (CEOI17_chase) C++14
0 / 100
 4000 ms 55692 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=-1){
  std::vector<long long> res(V+1,0);
  res[1]=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

chase.cpp: In function 'int main()':
chase.cpp:30: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:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&ps[i]);
     ~~~~~^~~~~~~~~~~~~
chase.cpp:36: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 Correct 4 ms 2684 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Incorrect 4 ms 2684 KB Output isn't correct
5 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 Correct 4 ms 2684 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Incorrect 4 ms 2684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4018 ms 55692 KB Time limit exceeded
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 Correct 4 ms 2684 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Incorrect 4 ms 2684 KB Output isn't correct
5 Halted 0 ms 0 KB -