oj.uz

Submission #561297

# Submission time Handle Problem Language Result Execution time Memory
561297 2022-05-12T15:26:26 Z fatemetmhr Chase (CEOI17_chase) C++17
0 / 100
 490 ms 296860 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 = 102;
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(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]);
            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] - (par == -1 ? 0 : a[par]) - a[v]);
    dp_az_oon[1][v][0] = -inf;
    memset(dp_az_oon[0][v], 0, sizeof dp_az_oon[0][v]);
    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] + a[v]);
            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] + valbanoon[v] - (par == -1 ? 0 : a[par]) - 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] - (par == -1 ? 0 : a[par]) - 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] - (par == -1 ? 0 : a[par]) - a[v]);
    dp_az_oon[1][v][0] = -inf;
    memset(dp_az_oon[0][v], 0, sizeof dp_az_oon[0][v]);
    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] + a[v]);
            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] + valbanoon[v] - (par == -1 ? 0 : a[par]) - 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] - (par == -1 ? 0 : a[par]) - 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 1 ms 2684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 1 ms 2684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 490 ms 296860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 1 ms 2684 KB Output isn't correct
3 Halted 0 ms 0 KB -