oj.uz

Submission #934310

# Submission time Handle Problem Language Result Execution time Memory
934310 2024-02-27T07:00:25 Z UmairAhmadMirza Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 91224 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e5+5;
int const V=103;
int dp[N][V];
int pei[N];
vector<int> adj[N];
void dfs(int node,int par=-1){
  for(auto i:adj[node]){
    if(i==par)
      continue;
    dfs(i,node);
  }
  for(int v=1;v<V;v++){
    int c1=0;
    int sm=0;
    for(auto i:adj[node]){
      if(i==par)
        continue;
      dp[node][v]=max(dp[node][v],dp[i][v]);
      c1=max(c1,pei[i]);
    }
    c1*=-1;
    for(auto i:adj[node]){
      if(i==par)
        continue;
      sm+=pei[i];
      c1=max(c1,dp[i][v-1]);
    }
    dp[node][v]=max(dp[node][v],sm+c1);
  }
  // cout<<node<<' '<<dp[node][0zzzzz]<<' '<<dp[node][1]<<' '<<dp[node][2]<<endl;
}
int ans=0;
int org_v;
void reroot(int a,int b){
  for(int v=1;v<=org_v;v++){
    dp[b][v]=0;
    int c1=0;
    int sm=0;
    for(auto i:adj[b]){
      if(i==a)
        continue;
      dp[b][v]=max(dp[b][v],dp[i][v]);
      c1=max(c1,pei[i]);
    }
    c1*=-1;
    for(auto i:adj[b]){
      if(i==a)
        continue;
      sm+=pei[i];
      c1=max(c1,dp[i][v-1]);
    }
    dp[b][v]=max(dp[b][v],sm+c1);
  }
  for(int v=1;v<=org_v;v++){
    dp[a][v]=0;
    int c1=0;
    int sm=0;
    for(auto i:adj[a]){
      dp[a][v]=max(dp[a][v],dp[i][v]);
      c1=max(c1,pei[i]);
    }
    c1*=-1;
    for(auto i:adj[a]){
      sm+=pei[i];
      c1=max(c1,dp[i][v-1]);
    }
    dp[a][v]=max(dp[a][v],sm+c1);
  }
}
void reroot_dfs(int node,int par){
  ans=max(ans,dp[node][org_v]);
  for(auto i:adj[node]){
    if(i==par)
      continue;
    reroot(i,node);
    reroot_dfs(i,node);
    reroot(node,i);
  }
}
signed main(){
  int n,v;
  cin>>n>>v;
  org_v=v;
  for(int i=1;i<=n;i++)
    cin>>pei[i];
  for(int i=0;i<n-1;i++){
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1);
  reroot_dfs(1,-1);
  cout<<ans<<endl;
  return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 28 ms 4700 KB Output is correct
10 Correct 5 ms 4952 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 90928 KB Output is correct
2 Correct 488 ms 91224 KB Output is correct
3 Execution timed out 4067 ms 88008 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 28 ms 4700 KB Output is correct
10 Correct 5 ms 4952 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 477 ms 90928 KB Output is correct
14 Correct 488 ms 91224 KB Output is correct
15 Execution timed out 4067 ms 88008 KB Time limit exceeded
16 Halted 0 ms 0 KB -