oj.uz

Submission #853542

# Submission time Handle Problem Language Result Execution time Memory
853542 2023-09-24T15:13:19 Z thanh913 Chase (CEOI17_chase) C++14
70 / 100
 611 ms 340756 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
using ll = long long;
 
const int N = 1e5+5;
 
template<class X, class Y>
bool cmax(X &a, const Y &b) {
    return a < b ? a = b, 1 : 0;
}
 
//--------------------------------------
int n, k, a[N];
vector<int> adj[N];

ll ans, up[N][105][2], down[N][105][2];
void dfs(int u, int pr) {
    ll s = 0;
    for (auto v : adj[u]) if (v != pr) {
        dfs(v, u);
        s += a[v];
    }
 
    up[u][0][0] = 0; up[u][1][1] = s;
    for (auto v : adj[u]) if (v != pr) {
        for (int i = 0; i <= k; i++) {
            cmax(up[u][i][0], max(up[v][i][0], up[v][i][1] + a[u]));
            if (i) {
                cmax(up[u][i][1], up[v][i-1][0] + s - a[v]);
                cmax(up[u][i][1], up[v][i-1][1] + s - a[v] + a[u]);
            }
        }
    }

    down[u][0][0] = 0; down[u][1][1] = 0;
    for (auto v : adj[u]) if (v != pr) {
        for (int i = 0; i <= k; i++) {
            cmax(down[u][i][0], max(down[v][i][0], down[v][i][1]));
            if (i) {
                cmax(down[u][i][1], down[v][i-1][0] + s);
                cmax(down[u][i][1], down[v][i-1][1] + s);
            }
        }
    }
    for (int i = 0; i <= k; i++) {
        cmax(ans, max(down[u][i][0], down[u][i][1] + a[pr]));
        cmax(ans, max(up[u][i][0], up[u][i][1]));
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int root = 1; root <= (n > 1e3 ? 1 : n); root++) {
        for (int i = 1; i <= n; i++) {
            memset(up[i], -63, sizeof(up[i]));
            memset(down[i], -63, sizeof(down[i]));
        }
        dfs(root, 0);
        
        for (int i = 0; i <= k; i++) {
            cmax(ans, max(up[root][i][0], up[root][i][1]));
            cmax(ans, max(down[root][i][0], down[root][i][1]));
        }
    }
    cout << ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 1 ms 4952 KB Output is correct
5 Correct 3 ms 4952 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 591 ms 7444 KB Output is correct
8 Correct 133 ms 7256 KB Output is correct
9 Correct 130 ms 7512 KB Output is correct
10 Correct 611 ms 7392 KB Output is correct
11 Correct 269 ms 7388 KB Output is correct
12 Correct 163 ms 7256 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 340636 KB Output is correct
2 Correct 158 ms 340756 KB Output is correct
3 Correct 114 ms 335304 KB Output is correct
4 Correct 94 ms 335184 KB Output is correct
5 Correct 179 ms 335152 KB Output is correct
6 Correct 184 ms 335200 KB Output is correct
7 Correct 180 ms 335188 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 1 ms 4952 KB Output is correct
5 Correct 3 ms 4952 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 591 ms 7444 KB Output is correct
8 Correct 133 ms 7256 KB Output is correct
9 Correct 130 ms 7512 KB Output is correct
10 Correct 611 ms 7392 KB Output is correct
11 Correct 269 ms 7388 KB Output is correct
12 Correct 163 ms 7256 KB Output is correct
13 Correct 171 ms 340636 KB Output is correct
14 Correct 158 ms 340756 KB Output is correct
15 Correct 114 ms 335304 KB Output is correct
16 Correct 94 ms 335184 KB Output is correct
17 Correct 179 ms 335152 KB Output is correct
18 Correct 184 ms 335200 KB Output is correct
19 Correct 180 ms 335188 KB Output is correct
20 Incorrect 183 ms 335200 KB Output isn't correct
21 Halted 0 ms 0 KB -