oj.uz

Submission #1111505

# Submission time Handle Problem Language Result Execution time Memory
1111505 2024-11-12T09:02:23 Z Zero_OP Chase (CEOI17_chase) C++14
100 / 100
 221 ms 227668 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 MAXN = 1e5 + 1;
const int MAXK = 105;

long long dp_s[MAXN][MAXK], dp_t[MAXN][MAXK]; //is the start, if choose u, used breadcumbs, at subtree u

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

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

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

    long long ans = 0;

    function<void(int, int)> dfs = [&](int u, int p){
        dp_s[u][1] = sum_neighbor[u];
        long long f = (p != -1 ? a[p] : 0);

        vector<long long> save_s(K + 1), save_t(K + 1);
        for(int v : adj[u]) if(v != p){
            dfs(v, u);
            for(int i = 1; i <= K; ++i){
                save_s[i] = max(dp_s[v][i], dp_s[v][i - 1] + sum_neighbor[u] - a[v]);
                save_t[i] = max(dp_t[v][i], dp_t[v][i - 1] + sum_neighbor[v] - a[u]);

                if(K - i > 0){
                    maximize(ans, dp_s[u][K - i] + save_t[i]);
                    maximize(ans, dp_t[u][K - i] + save_s[i]);
                }
            }

            for(int i = 1; i <= K; ++i){
                maximize(dp_s[u][i], save_s[i]);
                maximize(dp_t[u][i], save_t[i]);
            }
        }

        maximize(ans, dp_s[u][K]);
    };

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

    return 0;
}

Compilation message

chase.cpp: In lambda function:
chase.cpp:43:19: warning: unused variable 'f' [-Wunused-variable]
   43 |         long long f = (p != -1 ? a[p] : 0);
      |                   ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 2556 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 2556 KB Output is correct
7 Correct 3 ms 5964 KB Output is correct
8 Correct 2 ms 5200 KB Output is correct
9 Correct 2 ms 3152 KB Output is correct
10 Correct 3 ms 4924 KB Output is correct
11 Correct 2 ms 4944 KB Output is correct
12 Correct 2 ms 4944 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 225608 KB Output is correct
2 Correct 212 ms 225624 KB Output is correct
3 Correct 117 ms 91840 KB Output is correct
4 Correct 95 ms 138064 KB Output is correct
5 Correct 184 ms 140872 KB Output is correct
6 Correct 177 ms 139592 KB Output is correct
7 Correct 174 ms 139592 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 2556 KB Output is correct
7 Correct 3 ms 5964 KB Output is correct
8 Correct 2 ms 5200 KB Output is correct
9 Correct 2 ms 3152 KB Output is correct
10 Correct 3 ms 4924 KB Output is correct
11 Correct 2 ms 4944 KB Output is correct
12 Correct 2 ms 4944 KB Output is correct
13 Correct 210 ms 225608 KB Output is correct
14 Correct 212 ms 225624 KB Output is correct
15 Correct 117 ms 91840 KB Output is correct
16 Correct 95 ms 138064 KB Output is correct
17 Correct 184 ms 140872 KB Output is correct
18 Correct 177 ms 139592 KB Output is correct
19 Correct 174 ms 139592 KB Output is correct
20 Correct 156 ms 141128 KB Output is correct
21 Correct 27 ms 9296 KB Output is correct
22 Correct 159 ms 141896 KB Output is correct
23 Correct 106 ms 139336 KB Output is correct
24 Correct 171 ms 141508 KB Output is correct
25 Correct 116 ms 93348 KB Output is correct
26 Correct 221 ms 227668 KB Output is correct
27 Correct 219 ms 227528 KB Output is correct