oj.uz

Submission #853450

# Submission time Handle Problem Language Result Execution time Memory
853450 2023-09-24T11:14:28 Z manizare Chase (CEOI17_chase) C++14
100 / 100
 247 ms 173932 KB 
#include <bits/stdc++.h> 
 
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define Pii pair< pii , pii >
#define int long long
 
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn = 1e5 + 10 , maxq = 1e7 + 1 ,  inf = 1e18 + 10 , mod= 998244353 ,lg = 20 ;
int sm[maxn] , dp[maxn][102][2] , w[maxn] , ans = 0, n , k;
vector <int> G[maxn] ; 
int mx[102] ;
void dfs(int v, int p =0){
  sm[v] += w[p] ;
  for(int i =  0 ; i < G[v].size() ; i++){
    int u = G[v][i] ;
    if(u == p)continue ;
    sm[v] += w[u];
    dfs(u , v) ;
  }
  for(int i =0 ; i < G[v].size() ; i++){
    int u= G[v][i] ;
    if(u==p)continue ;
    for(int i =0 ; i <= k ; i++){
      if(i!=0)ans = max(ans , dp[u][i-1][0] + sm[v]) ;
      dp[v][i][0] = max({dp[v][i][0] , dp[u][i][0] , (i!=0 ?dp[u][i-1][0] + sm[v] - w[p] : -inf)});
    }
    for(int i =0 ; i <= k ; i++){
      dp[v][i][1] = max({dp[v][i][1] , dp[u][i][1] , (i!=0 ?dp[u][i-1][1] + sm[v] - w[u]: -inf)});
    }
  }
  for(int i = 0 ; i <= k ; i++){
    if(i!=0)dp[v][i][0] = max(dp[v][i][0] , sm[v]-w[p]) ;
    if(i!=0)dp[v][i][1] = max(dp[v][i][1] , sm[v]) ;
    ans = max(ans , dp[v][i][1]) ;
  }
  ans = max(ans , sm[v]) ;
  for(int i = 0 ; i <= k ; i++)mx[i] =0 ; 
  mx[0] = -1 ;
  for(int i = 0 ; i < G[v].size() ; i++){
    int u = G[v][i] ;
    if(u == p)continue ;
    if(mx[0]!=-1){
      for(int i = 1 ; i <k ; i++){
        ans = max(ans , mx[k-i] + dp[u][i][1]) ;
      }
      for(int i = 2;  i < k ; i++){
        ans = max(ans,mx[k-i] + dp[u][i-1][1] + sm[v] - w[u]) ;
      }
    }
    for(int i =0 ; i <= k ; i++){
      mx[i] = max(mx[i] , dp[u][i][0]) ;
    }
  }
  reverse(all(G[v]));
  for(int i = 0 ; i <= k ; i++)mx[i] =0 ; 
  mx[0] = -1 ;
  for(int i = 0 ; i < G[v].size() ; i++){
    int u = G[v][i] ;
    if(u == p)continue ;
    if(mx[0]!=-1){
      for(int i = 1 ; i <k ; i++){
        ans = max(ans , mx[k-i] + dp[u][i][1]) ;
      }
      for(int i = 2;  i < k ; i++){
        ans = max(ans,mx[k-i] + dp[u][i-1][1] + sm[v] - w[u]) ;
      }
    }
    for(int i =0 ; i <= k ; i++){
      mx[i] = max(mx[i] , dp[u][i][0]) ;
    }
  }
}
signed main(){
  ios::sync_with_stdio(false); cin.tie(0) ;
  cin >> n >> k ;
  for(int i = 1; i <= n ; i++){
    cin >> w[i] ;
  }
  for(int i = 1; i < n; i++){
    int v, u ;
    cin >> v>> u ;
    G[v].pb(u);G[u].pb(v) ; 
  }
  if(k ==0 ){
    cout << 0 ;
    return 0 ;
  }
  dfs(1 , 0) ;
  cout << ans ; 
}
/*
15909907109
*/

Compilation message

chase.cpp: In function 'void dfs(long long int, long long int)':
chase.cpp:20:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int i =  0 ; i < G[v].size() ; i++){
      |                    ~~^~~~~~~~~~~~~
chase.cpp:26:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i =0 ; i < G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~
chase.cpp:45:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i = 0 ; i < G[v].size() ; i++){
      |                   ~~^~~~~~~~~~~~~
chase.cpp:63:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 0 ; i < G[v].size() ; i++){
      |                   ~~^~~~~~~~~~~~~

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 4696 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4696 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 4696 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5208 KB Output is correct
12 Correct 2 ms 5208 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 173932 KB Output is correct
2 Correct 211 ms 173924 KB Output is correct
3 Correct 230 ms 167876 KB Output is correct
4 Correct 128 ms 167788 KB Output is correct
5 Correct 227 ms 167784 KB Output is correct
6 Correct 247 ms 167768 KB Output is correct
7 Correct 233 ms 167760 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5208 KB Output is correct
12 Correct 2 ms 5208 KB Output is correct
13 Correct 217 ms 173932 KB Output is correct
14 Correct 211 ms 173924 KB Output is correct
15 Correct 230 ms 167876 KB Output is correct
16 Correct 128 ms 167788 KB Output is correct
17 Correct 227 ms 167784 KB Output is correct
18 Correct 247 ms 167768 KB Output is correct
19 Correct 233 ms 167760 KB Output is correct
20 Correct 230 ms 167760 KB Output is correct
21 Correct 28 ms 8272 KB Output is correct
22 Correct 229 ms 167760 KB Output is correct
23 Correct 124 ms 167716 KB Output is correct
24 Correct 232 ms 167712 KB Output is correct
25 Correct 227 ms 168048 KB Output is correct
26 Correct 215 ms 173904 KB Output is correct
27 Correct 214 ms 173848 KB Output is correct