oj.uz

Submission #561310

# Submission time Handle Problem Language Result Execution time Memory
561310 2022-05-12T15:39:59 Z fatemetmhr Chase (CEOI17_chase) C++17
100 / 100
 642 ms 346044 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long    ll;
typedef pair<ll, ll> pll;

#define pb      push_back
#define all(x)  x.begin(), x.end()
#define fi      first
#define se      second
#define mp      make_pair

const int maxn5  = 1e5 + 5;
const int mxnoon = 105;
const ll  inf    = 1e18;


ll valbanoon[maxn5];
ll a[maxn5], limlim, ans = 0;
vector <int> adj[maxn5];
ll dp_az_oon[2][maxn5][mxnoon], dp_be_oon[2][maxn5][mxnoon]; 

// dp[1] -> akharesh noon hast, 0 -> nist
// dp barabare ba TOM - JERRY

inline void dfs_be_oon_ja(int v, int par){
    dp_be_oon[1][v][0] = -inf;
    for(int lim = 1; lim <= limlim; lim++){
        dp_be_oon[1][v][lim] = valbanoon[v] - (par == -1 ? 0 : a[par]) - a[v];
        dp_be_oon[0][v][lim] = a[v];
    }
    dp_be_oon[0][v][0] = a[v];
    for(auto u : adj[v]) if(u != par){
        dfs_be_oon_ja(u, v);
        for(int lim = 0; lim <= limlim; lim++){
            dp_be_oon[0][v][lim] = max(dp_be_oon[0][v][lim], dp_be_oon[1][u][lim] + a[v]); // farz shode ishoon avale araye nistan
            dp_be_oon[0][v][lim] = max(dp_be_oon[0][v][lim], dp_be_oon[0][u][lim] - a[u] + a[v]);
            if(lim)
                dp_be_oon[1][v][lim] = max(dp_be_oon[1][v][lim], dp_be_oon[1][u][lim - 1] + valbanoon[v] - (par == -1 ? 0 : a[par]) - a[v]);
            if(lim)
                dp_be_oon[1][v][lim] = max(dp_be_oon[1][v][lim], dp_be_oon[0][u][lim - 1] + valbanoon[v] - (par == -1 ? 0 : a[par]) - a[u] - a[v]);
        }
    }
    return;
}

inline void dfs_az_oon_ja(int v, int par){
    for(auto u : adj[v]) if(u != par){
        dfs_az_oon_ja(u, v);
    }
    fill(dp_az_oon[1][v], dp_az_oon[1][v] + limlim + 2, valbanoon[v] - a[v]);
    dp_az_oon[1][v][0] = -inf;
    memset(dp_az_oon[0][v], 0, sizeof dp_az_oon[0][v]); // inja sare arayast .. pas har do mibinn
    for(auto u : adj[v]) if(u != par){
        for(int lim = 0; lim <= limlim; lim++){ // lim rooye tedad nan ha dar ta root
            ans = max(ans, dp_az_oon[0][v][lim] + dp_be_oon[0][u][limlim - lim] - a[u]);
            ans = max(ans, dp_az_oon[0][v][lim] + dp_be_oon[1][u][limlim - lim]);
            ans = max(ans, dp_az_oon[1][v][lim] + dp_be_oon[0][u][limlim - lim] - a[u]);
            ans = max(ans, dp_az_oon[1][v][lim] + dp_be_oon[1][u][limlim - lim]);
        }
        for(int lim = 0; lim <= limlim; lim++){
            dp_az_oon[0][v][lim] = max(dp_az_oon[0][v][lim], dp_az_oon[1][u][lim]);
            dp_az_oon[0][v][lim] = max(dp_az_oon[0][v][lim], dp_az_oon[0][u][lim]);
            if(lim)
                dp_az_oon[1][v][lim] = max(dp_az_oon[1][v][lim], dp_az_oon[1][u][lim - 1] - a[v] + valbanoon[v] - a[u]);
            if(lim)
                dp_az_oon[1][v][lim] = max(dp_az_oon[1][v][lim], dp_az_oon[0][u][lim - 1] + valbanoon[v] - a[u] - a[v]);
        }
        for(int lim = 1; lim <= limlim; lim++){
            dp_az_oon[0][v][lim] = max(dp_az_oon[0][v][lim], dp_az_oon[0][v][lim - 1]);
            dp_az_oon[1][v][lim] = max(dp_az_oon[1][v][lim], dp_az_oon[1][v][lim - 1]);
        }
    }
    reverse(all(adj[v]));
    fill(dp_az_oon[1][v], dp_az_oon[1][v] + limlim + 2, valbanoon[v] - a[v]);
    dp_az_oon[1][v][0] = -inf;
    memset(dp_az_oon[0][v], 0, sizeof dp_az_oon[0][v]); // inja sare arayast .. pas har do mibinn
    for(auto u : adj[v]) if(u != par){
        for(int lim = 0; lim <= limlim; lim++){ // lim rooye tedad nan ha dar ta root
            ans = max(ans, dp_az_oon[0][v][lim] + dp_be_oon[0][u][limlim - lim] - a[u]);
            ans = max(ans, dp_az_oon[0][v][lim] + dp_be_oon[1][u][limlim - lim]);
            ans = max(ans, dp_az_oon[1][v][lim] + dp_be_oon[0][u][limlim - lim] - a[u]);
            ans = max(ans, dp_az_oon[1][v][lim] + dp_be_oon[1][u][limlim - lim]);
        }
        for(int lim = 0; lim <= limlim; lim++){
            dp_az_oon[0][v][lim] = max(dp_az_oon[0][v][lim], dp_az_oon[1][u][lim]);
            dp_az_oon[0][v][lim] = max(dp_az_oon[0][v][lim], dp_az_oon[0][u][lim]);
            if(lim)
                dp_az_oon[1][v][lim] = max(dp_az_oon[1][v][lim], dp_az_oon[1][u][lim - 1] - a[v] + valbanoon[v] - a[u]);
            if(lim)
                dp_az_oon[1][v][lim] = max(dp_az_oon[1][v][lim], dp_az_oon[0][u][lim - 1] + valbanoon[v] - a[u] - a[v]);
        }
        for(int lim = 1; lim <= limlim; lim++){
            dp_az_oon[0][v][lim] = max(dp_az_oon[0][v][lim], dp_az_oon[0][v][lim - 1]);
            dp_az_oon[1][v][lim] = max(dp_az_oon[1][v][lim], dp_az_oon[1][v][lim - 1]);
        }
    }
    ans = max({ans, dp_az_oon[0][v][limlim], dp_az_oon[1][v][limlim]});
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n; cin >> n >> limlim;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        valbanoon[i] = a[i];
    }
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    for(int i = 0; i < n; i++) for(auto u : adj[i])
        valbanoon[i] += a[u];

    dfs_be_oon_ja(0, -1);
    dfs_az_oon_ja(0, -1);

    if(limlim){
        for(int i = 0; i < n; i++)
            ans = max(ans, valbanoon[i] - a[i]);
    }

    cout << ans << endl;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 7 ms 6044 KB Output is correct
8 Correct 4 ms 6100 KB Output is correct
9 Correct 4 ms 5972 KB Output is correct
10 Correct 9 ms 5972 KB Output is correct
11 Correct 7 ms 5972 KB Output is correct
12 Correct 5 ms 6024 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 343844 KB Output is correct
2 Correct 596 ms 345936 KB Output is correct
3 Correct 513 ms 338580 KB Output is correct
4 Correct 299 ms 338252 KB Output is correct
5 Correct 628 ms 338324 KB Output is correct
6 Correct 642 ms 338332 KB Output is correct
7 Correct 636 ms 338352 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 7 ms 6044 KB Output is correct
8 Correct 4 ms 6100 KB Output is correct
9 Correct 4 ms 5972 KB Output is correct
10 Correct 9 ms 5972 KB Output is correct
11 Correct 7 ms 5972 KB Output is correct
12 Correct 5 ms 6024 KB Output is correct
13 Correct 593 ms 343844 KB Output is correct
14 Correct 596 ms 345936 KB Output is correct
15 Correct 513 ms 338580 KB Output is correct
16 Correct 299 ms 338252 KB Output is correct
17 Correct 628 ms 338324 KB Output is correct
18 Correct 642 ms 338332 KB Output is correct
19 Correct 636 ms 338352 KB Output is correct
20 Correct 637 ms 338424 KB Output is correct
21 Correct 285 ms 338248 KB Output is correct
22 Correct 612 ms 338332 KB Output is correct
23 Correct 284 ms 338216 KB Output is correct
24 Correct 614 ms 338316 KB Output is correct
25 Correct 502 ms 338232 KB Output is correct
26 Correct 586 ms 346028 KB Output is correct
27 Correct 529 ms 346044 KB Output is correct