oj.uz

답안 #593469

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
593469 2022-07-11T08:47:16 Z alextodoran Chase (CEOI17_chase) C++17
100 / 100
 462 ms 180060 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = (int) 1e5;
const int K_MAX = 100;

int N, K;
int P[N_MAX + 2];
vector <int> adj[N_MAX + 2];

ll down[N_MAX + 2][K_MAX + 2];
ll up[N_MAX + 2][K_MAX + 2];
ll full[N_MAX + 2];

ll maxDown[K_MAX + 2];

void dfs (int u, int parent = 0) {
    vector <int> sons;
    ll sumSons = 0;
    for (int v : adj[u]) {
        if (v != parent) {
            sons.push_back(v);
            dfs(v, u);
            sumSons += P[v];
        }
    }
    down[u][0] = 0;
    down[u][1] = sumSons;
    up[u][0] = 0;
    up[u][1] = sumSons + P[parent];
    for (int v : sons) {
        for (int k = 0; k <= K; k++) {
            down[u][k] = max(down[u][k], down[v][k]);
            up[u][k] = max(up[u][k], up[v][k]);
            if (k > 0) {
                down[u][k] = max(down[u][k], down[v][k - 1] + sumSons);
                up[u][k] = max(up[u][k], up[v][k - 1] + sumSons - P[v] + P[parent]);
            }
        }
        full[u] = max(full[u], full[v]);
    }
    for (int k = 1; k <= K; k++) {
        down[u][k] = max(down[u][k], down[u][k - 1]);
        up[u][k] = max(up[u][k], up[u][k - 1]);
    }
    fill(maxDown, maxDown + K + 1, 0);
    for (int v : sons) {
        for (int k = 0; k <= K; k++) {
            full[u] = max(full[u], up[v][k] + maxDown[K - k]);
            if (k < K) {
                full[u] = max(full[u], up[v][k] + maxDown[K - k - 1] + sumSons - P[v] + P[parent]);
            }
            full[u] = max(full[u], down[v][k]);
            if (k > 0) {
                full[u] = max(full[u], down[v][k - 1] + sumSons + P[parent]);
            }
        }
        for (int k = 0; k <= K; k++) {
            maxDown[k] = max(maxDown[k], down[v][k]);
        }
    }
    reverse(sons.begin(), sons.end());
    fill(maxDown, maxDown + K + 1, 0);
    for (int v : sons) {
        for (int k = 0; k <= K; k++) {
            full[u] = max(full[u], up[v][k] + maxDown[K - k]);
            if (k < K) {
                full[u] = max(full[u], up[v][k] + maxDown[K - k - 1] + sumSons - P[v] + P[parent]);
            }
        }
        for (int k = 0; k <= K; k++) {
            maxDown[k] = max(maxDown[k], down[v][k]);
        }
    }
}

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

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

    dfs(1);
    cout << full[1] << "\n";

    return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 2 ms 2644 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 5 ms 4436 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 5 ms 4308 KB Output is correct
11 Correct 4 ms 4308 KB Output is correct
12 Correct 3 ms 4308 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 345 ms 177904 KB Output is correct
2 Correct 337 ms 178292 KB Output is correct
3 Correct 371 ms 167180 KB Output is correct
4 Correct 125 ms 167072 KB Output is correct
5 Correct 339 ms 167140 KB Output is correct
6 Correct 341 ms 166936 KB Output is correct
7 Correct 335 ms 166940 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 5 ms 4436 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 5 ms 4308 KB Output is correct
11 Correct 4 ms 4308 KB Output is correct
12 Correct 3 ms 4308 KB Output is correct
13 Correct 345 ms 177904 KB Output is correct
14 Correct 337 ms 178292 KB Output is correct
15 Correct 371 ms 167180 KB Output is correct
16 Correct 125 ms 167072 KB Output is correct
17 Correct 339 ms 167140 KB Output is correct
18 Correct 341 ms 166936 KB Output is correct
19 Correct 335 ms 166940 KB Output is correct
20 Correct 345 ms 168812 KB Output is correct
21 Correct 126 ms 168788 KB Output is correct
22 Correct 462 ms 168824 KB Output is correct
23 Correct 146 ms 168844 KB Output is correct
24 Correct 350 ms 168916 KB Output is correct
25 Correct 336 ms 168504 KB Output is correct
26 Correct 335 ms 180048 KB Output is correct
27 Correct 331 ms 180060 KB Output is correct