oj.uz

Submission #934307

# Submission time Handle Problem Language Result Execution time Memory
934307 2024-02-27T06:57:29 Z UmairAhmadMirza Chase (CEOI17_chase) C++14
40 / 100
 4000 ms 91140 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<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<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 4696 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 4696 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 4696 KB Output is correct
8 Correct 5 ms 4696 KB Output is correct
9 Correct 522 ms 4740 KB Output is correct
10 Correct 5 ms 4696 KB Output is correct
11 Correct 6 ms 4696 KB Output is correct
12 Correct 7 ms 4700 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 91016 KB Output is correct
2 Correct 503 ms 91140 KB Output is correct
3 Execution timed out 4074 ms 88064 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 4696 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 4696 KB Output is correct
8 Correct 5 ms 4696 KB Output is correct
9 Correct 522 ms 4740 KB Output is correct
10 Correct 5 ms 4696 KB Output is correct
11 Correct 6 ms 4696 KB Output is correct
12 Correct 7 ms 4700 KB Output is correct
13 Correct 505 ms 91016 KB Output is correct
14 Correct 503 ms 91140 KB Output is correct
15 Execution timed out 4074 ms 88064 KB Time limit exceeded
16 Halted 0 ms 0 KB -