oj.uz

Submission #853367

# Submission time Handle Problem Language Result Execution time Memory
853367 2023-09-24T08:45:48 Z manizare Chase (CEOI17_chase) C++14
70 / 100
 281 ms 173204 KB 
#include <bits/stdc++.h> 
 
#pragma GCC optimize("O3,unroll-loops")
#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 dis[maxn] , k , n  , w[maxn] , dp[maxn][102][2] , sm[maxn]; 
vector <int> G[maxn] ;
int ans= 0 ; 
 
void dfs(int v, int p =0 ){
  sm[v] = 0 ;
  for(int i =0 ; i < G[v].size() ; i++){
    int u =G[v][i] ;
    if(u == p)continue ;
    sm[v] += w[u] ;
  }
  for(int i = 1 ; i <= k ; i++){
    dp[v][i][0] = max(dp[p][i][1] , dp[p][i][0])  ;
    dp[v][i][1] = max(dp[p][i-1][1] + sm[v] ,   dp[p][i-1][0] + sm[v]) ;
    ans= max({ans , dp[v][i][1] , dp[v][i][0]}) ; 
  }
  for(int i =0 ; i < G[v].size() ; i++){
    int u =G[v][i] ;
    if(u == p)continue ;
    dfs(u, v);  
  }
}
 
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 = 0 ; i <= k ; i++){
    dp[0][i][1] = -inf ;
    dp[0][i][0] = -inf ;
  }
  dp[0][0][0] = 0 ;
  for(int i = 1; i < n; i++){
    int v, u ;
    cin >> v>> u ;
    G[v].pb(u);G[u].pb(v) ; 
  }
  if(n > 1000){
    dfs(1 , 0);
    cout << ans ;
    return 0 ;
  }
  for(int i = 1; i <= n ; i++){
    dfs(i , 0);
  }
  cout << ans ; 
}

Compilation message

chase.cpp: In function 'void dfs(long long int, long long int)':
chase.cpp:22: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]
   22 |   for(int i =0 ; i < G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~
chase.cpp:32: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]
   32 |   for(int i =0 ; i < G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 7000 KB Output is correct
7 Correct 281 ms 8908 KB Output is correct
8 Correct 33 ms 8792 KB Output is correct
9 Correct 28 ms 8792 KB Output is correct
10 Correct 257 ms 8860 KB Output is correct
11 Correct 95 ms 8864 KB Output is correct
12 Correct 32 ms 8796 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 173140 KB Output is correct
2 Correct 97 ms 173204 KB Output is correct
3 Correct 67 ms 168736 KB Output is correct
4 Correct 56 ms 168460 KB Output is correct
5 Correct 109 ms 168520 KB Output is correct
6 Correct 105 ms 168276 KB Output is correct
7 Correct 102 ms 168524 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 7000 KB Output is correct
7 Correct 281 ms 8908 KB Output is correct
8 Correct 33 ms 8792 KB Output is correct
9 Correct 28 ms 8792 KB Output is correct
10 Correct 257 ms 8860 KB Output is correct
11 Correct 95 ms 8864 KB Output is correct
12 Correct 32 ms 8796 KB Output is correct
13 Correct 95 ms 173140 KB Output is correct
14 Correct 97 ms 173204 KB Output is correct
15 Correct 67 ms 168736 KB Output is correct
16 Correct 56 ms 168460 KB Output is correct
17 Correct 109 ms 168520 KB Output is correct
18 Correct 105 ms 168276 KB Output is correct
19 Correct 102 ms 168524 KB Output is correct
20 Incorrect 108 ms 168524 KB Output isn't correct
21 Halted 0 ms 0 KB -