oj.uz

답안 #593467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
593467 2022-07-11T08:40:45 Z alextodoran Chase (CEOI17_chase) C++17
50 / 100
 400 ms 180300 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]);
            }
        }
        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]);
        }
    }
    for (int k = 0; k <= K; k++) {
        full[u] = max(full[u], down[u][k]);
        full[u] = max(full[u], up[u][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 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Incorrect 5 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 400 ms 178296 KB Output is correct
2 Correct 393 ms 180300 KB Output is correct
3 Correct 346 ms 169708 KB Output is correct
4 Correct 127 ms 168780 KB Output is correct
5 Correct 360 ms 168856 KB Output is correct
6 Correct 384 ms 168820 KB Output is correct
7 Correct 382 ms 168872 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Incorrect 5 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -