oj.uz

Submission #511984

# Submission time Handle Problem Language Result Execution time Memory
511984 2022-01-16T05:48:07 Z Monarchuwu Chase (CEOI17_chase) C++17
100 / 100
 447 ms 317284 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e5 + 9, K = 100 + 2;
int n, V;
int p[N];
vector<int> g[N];
ll sum_p[N];

ll dp1[N][K];   // dp1[u][j]: bắt đầu tại u, sẽ dùng j lượt (đi vào subtree)
void dfs_1(int u, int par) {
    for (int v : g[u]) if (v != par) {
        dfs_1(v, u);
        for (int j = 1; j <= V; ++j) {
            dp1[u][j] = max({ dp1[u][j], dp1[v][j], dp1[v][j - 1] + sum_p[v] - p[u] });
        }
    }
}
ll dp2[N][K];   // dp2[u][j]: bắt đầu tại u, sẽ dùng j lượt (đi lên root)
ll tmp[K];
ll prf[N][K], suf[N][K];
void dfs_2(int u, int par) {

    fill(tmp, tmp + V + 1, 0);
    for (int v : g[u]) if (v != par) {
        copy(tmp, tmp + V + 1, prf[v]);
        for (int j = 1; j <= V; ++j) {
            tmp[j] = max({ tmp[j], dp1[v][j], dp1[v][j - 1] + sum_p[v] - p[u] });
        }
    }

    reverse(all(g[u]));
    fill(tmp, tmp + V + 1, 0);
    for (int v : g[u]) if (v != par) {
        copy(tmp, tmp + V + 1, suf[v]);
        for (int j = 1; j <= V; ++j) {
            tmp[j] = max({ tmp[j], dp1[v][j], dp1[v][j - 1] + sum_p[v] - p[u] });
        }
    }
    reverse(all(g[u]));

    for (int v : g[u]) if (v != par) {

        copy(dp2[u], dp2[u] + V + 1, tmp);
        for (int j = 1; j <= V; ++j) {
            tmp[j] = max({ tmp[j], prf[v][j], suf[v][j] });
        }

        for (int j = 1; j <= V; ++j) {
            dp2[v][j] = max({ dp2[v][j], tmp[j], tmp[j - 1] + sum_p[u] - p[v] });
        }

        dfs_2(v, u);
    }
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> p[i];
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int u = 1; u <= n; ++u)
        for (int v : g[u]) sum_p[u] += p[v];

    dfs_1(1, 0);
    dfs_2(1, 0);
    ll ans(0);
    for (int u = 1; u <= n; ++u) {
        ans = max({ ans, dp1[u][V], dp2[u][V] });
        for (int j = 0; j < V; ++j) {
            ans = max(ans, max(dp1[u][j], dp2[u][j]) + sum_p[u]);
        }
    }
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
36
--------------------------------------------------|
==================================================+
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 4 ms 5632 KB Output is correct
8 Correct 5 ms 5628 KB Output is correct
9 Correct 4 ms 5112 KB Output is correct
10 Correct 5 ms 5836 KB Output is correct
11 Correct 5 ms 5836 KB Output is correct
12 Correct 4 ms 5760 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 294780 KB Output is correct
2 Correct 356 ms 294720 KB Output is correct
3 Correct 228 ms 249148 KB Output is correct
4 Correct 247 ms 315164 KB Output is correct
5 Correct 436 ms 317168 KB Output is correct
6 Correct 411 ms 317216 KB Output is correct
7 Correct 447 ms 317284 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 4 ms 5632 KB Output is correct
8 Correct 5 ms 5628 KB Output is correct
9 Correct 4 ms 5112 KB Output is correct
10 Correct 5 ms 5836 KB Output is correct
11 Correct 5 ms 5836 KB Output is correct
12 Correct 4 ms 5760 KB Output is correct
13 Correct 373 ms 294780 KB Output is correct
14 Correct 356 ms 294720 KB Output is correct
15 Correct 228 ms 249148 KB Output is correct
16 Correct 247 ms 315164 KB Output is correct
17 Correct 436 ms 317168 KB Output is correct
18 Correct 411 ms 317216 KB Output is correct
19 Correct 447 ms 317284 KB Output is correct
20 Correct 409 ms 317176 KB Output is correct
21 Correct 151 ms 169052 KB Output is correct
22 Correct 430 ms 317064 KB Output is correct
23 Correct 234 ms 315200 KB Output is correct
24 Correct 444 ms 317264 KB Output is correct
25 Correct 237 ms 248824 KB Output is correct
26 Correct 344 ms 294856 KB Output is correct
27 Correct 363 ms 294848 KB Output is correct