oj.uz

답안 #1111335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1111335 2024-11-12T06:24:12 Z Zero_OP Chase (CEOI17_chase) C++14
0 / 100
 186 ms 102728 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        } return false;
    }

const int MAX_N = 1e5 + 5;
const int MAX_K = 100 + 5;

int N, K, p[MAX_N];
long long sum_neighbor[MAX_N];
vector<int> adj[MAX_N];
long long f[MAX_N][MAX_K], g[MAX_N][MAX_K], ans;

//f[u][i] = if p[u] > 0
//g[u][i] = if p[u] = 0

void dfs(int u, int pre){
    for(int v : adj[u]) if(v != pre){
        dfs(v, u);
    }

    for(int v : adj[u]) if(v != pre){
        for(int i = 1; i <= K; ++i){
            maximize(f[u][i], max(f[v][i - 1] - (i == 1 ? 0 : p[v]), g[v][i - 1] - p[v]) + sum_neighbor[u]);
            maximize(g[u][i], f[v][i]);
        }
    }

    vector<long long> info_f(K + 1, 0);
    vector<long long> info_g(K + 1, 0);
    vector<long long> info_g_sub(K + 1, 0);
    vector<long long> info_f_sub(K + 1, 0);

    /*
    Case 1 : drop breadcumb at u
    if both empty : g[v1][i] + g[v2][j] + sum_neighbor[u] - p[v1] - p[v2]
    if the previous is empty and the current is not empty : g[v1][i] + f[v2][j] + sum_neighbor[u] - p[v1]
    if the previous is not empty, but the current is empty : f[v1][i] + g[v2][j] + sum_neghbor[u] - p[v2]
    if both not empty : f[v1][i] + f[v2][j] + sum_neighbor[u]

    Case 2 : not drop a breadcumb at u
    if both empty : g[v1][i] + g[v2][j]
    if the previous is empty and the current is not empty : g[v1][i] + f[v2][j]
    if the previous is not empty, but the current is empty : f[v1][i] + g[v2][j]
    if both not empty : f[v1][i] + g[v2][j]

    */

    maximize(ans, max(f[u][K], g[u][K]));

    bool exist_subtrees = false;
    for(int v : adj[u]) if(v != pre){

        if(exist_subtrees){
            //drop breadcumb at u
            for(int i = 0; i < K; ++i){
                //both is empty
                maximize(ans, info_g_sub[i] + g[v][K - i - 1] + sum_neighbor[u]);

                //previous is empty, p[v] is still
                maximize(ans, info_g_sub[i] + f[v][K - i - 1] + sum_neighbor[u] - p[v]);

                //previous is not empty, but p[v] is empty
                maximize(ans, info_f_sub[i] + g[v][K - i - 1] + sum_neighbor[u]);

                //both not empty
                maximize(ans, info_f_sub[i] + f[v][K - i - 1] + sum_neighbor[u] - p[v]);
            }

            //not drop breadcumb at u
            for(int i = 0; i <= K; ++i){
                //both is empty
                maximize(ans, info_g[i] + g[v][K - i]);

                //previous is empty, p[v] is still
                maximize(ans, info_g[i] + f[v][K - i]);

                //previous is not empty, but p[v] is empty
                maximize(ans, info_f[i] + g[v][K - i]);

                //bot not empty
                maximize(ans, info_f[i] + f[v][K - i] - p[u]); //duplicated
            }
        }

        exist_subtrees = true;

        //update info
        for(int i = 1; i <= K; ++i){
            maximize(info_f[i], f[v][i]);
            maximize(info_g[i], g[v][i]);

            maximize(info_f_sub[i], f[v][i] - p[v]);
            maximize(info_g_sub[i], g[v][i] - p[v]);
        }
    }
}

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N >> K;
    for(int i = 0; i < N; ++i) cin >> p[i];
    for(int i = 0; i < N - 1; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
        sum_neighbor[u] += p[v];
        sum_neighbor[v] += p[u];
    }

    if(K == 0){
        cout << 0 << '\n';
        return 0;
    }

    dfs(1, -1);
    cout << ans << '\n';

    return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 186 ms 102728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2896 KB Output isn't correct
2 Halted 0 ms 0 KB -