oj.uz

Submission #419145

# Submission time Handle Problem Language Result Execution time Memory
419145 2021-06-06T13:28:34 Z egekabas Chase (CEOI17_chase) C++14
100 / 100
 398 ms 271456 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll n, k;
ll p[100009];
vector<ll> g[100009];
ll dpup[100009][109];
ll dpdown[100009][109][2];
ll ans;
void dfs(ll v, ll prt){
    ll neig = 0;
    for(auto u : g[v]){
        neig += p[u];
        if(u != prt){
            dfs(u, v);
            for(ll i = 0; i <= k; ++i)
                dpdown[u][i][1] -= p[v];
        }
    }


    dpup[v][1] = neig;
    dpdown[v][1][1] = neig;
    for(auto u : g[v])
        if(u != prt){
            for(ll i = 0; i <= k; ++i){
                ans = max(ans, dpup[v][k-i]+dpdown[u][i][0]);
                ans = max(ans, dpup[v][k-i]+dpdown[u][i][1]);
            
                ans = max(ans, dpdown[v][k-i][0]+dpup[u][i]);
                ans = max(ans, dpdown[v][k-i][1]+dpup[u][i]-p[u]);
            }
            
            for(ll i = 0; i <= k; ++i){
                dpup[v][i] = max(dpup[v][i], dpup[u][i]);
                if(i){
                    dpup[v][i] = max(dpup[v][i], dpup[u][i-1]+neig-p[u]);
                    dpup[v][i] = max(dpup[v][i], dpup[v][i-1]);
                }
            }
            for(ll i = 0; i <= k; ++i){
                dpdown[v][i][0] = max({dpdown[v][i][0], dpdown[u][i][0], dpdown[u][i][1]});
                if(i){
                    dpdown[v][i][0] = max(dpdown[v][i][0], dpdown[v][i-1][0]);
                    dpdown[v][i][1] = max({dpdown[v][i][1], dpdown[v][i-1][1], dpdown[u][i-1][0]+neig, dpdown[u][i-1][1]+neig});
                }
            }
        }
    
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> k;
    for(ll i = 1; i <= n; ++i)
        cin >> p[i];
    for(ll i = 1; i < n; ++i){
        ll a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs(1, 0);
    cout << ans << '\n';   
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 4 ms 5260 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 6 ms 5196 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 4 ms 5196 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 269284 KB Output is correct
2 Correct 370 ms 271320 KB Output is correct
3 Correct 290 ms 265380 KB Output is correct
4 Correct 209 ms 265156 KB Output is correct
5 Correct 398 ms 265180 KB Output is correct
6 Correct 386 ms 265124 KB Output is correct
7 Correct 381 ms 265240 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 4 ms 5260 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 6 ms 5196 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 4 ms 5196 KB Output is correct
13 Correct 380 ms 269284 KB Output is correct
14 Correct 370 ms 271320 KB Output is correct
15 Correct 290 ms 265380 KB Output is correct
16 Correct 209 ms 265156 KB Output is correct
17 Correct 398 ms 265180 KB Output is correct
18 Correct 386 ms 265124 KB Output is correct
19 Correct 381 ms 265240 KB Output is correct
20 Correct 383 ms 265304 KB Output is correct
21 Correct 203 ms 265216 KB Output is correct
22 Correct 386 ms 265288 KB Output is correct
23 Correct 203 ms 265188 KB Output is correct
24 Correct 378 ms 265224 KB Output is correct
25 Correct 285 ms 265012 KB Output is correct
26 Correct 346 ms 271428 KB Output is correct
27 Correct 347 ms 271456 KB Output is correct