oj.uz

Submission #853538

# Submission time Handle Problem Language Result Execution time Memory
853538 2023-09-24T14:45:33 Z thanh913 Chase (CEOI17_chase) C++14
40 / 100
 268 ms 175020 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 f[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];
    }
 
    f[u][0][0] = 0; f[u][1][1] = s;
    for (auto v : adj[u]) if (v != pr) {
        for (int i = 0; i <= k; i++) {
            cmax(f[u][i][0], max(f[v][i][0], f[v][i][1] + a[u]));
            if (i) {
                cmax(f[u][i][1], f[v][i-1][0] + s - a[v]);
                cmax(f[u][i][1], f[v][i-1][1] + s - a[v] + a[u]);
            }
        }
    }
}
 
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);
    }
 
    ll ans = 0;
    for (int root = 1; root <= (n > 1e3 ? 1 : n); root++) { // doi
        for (int i = 1; i <= n; i++) {
            memset(f[i], -63, sizeof(f[i]));
        }
        dfs(root, root);
        
        for (int i = 0; i <= k; i++) {
            cmax(ans, max(f[root][i][0], f[root][i][1]));
        }
    }
    cout << ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 263 ms 5140 KB Output is correct
8 Correct 66 ms 5144 KB Output is correct
9 Correct 66 ms 5112 KB Output is correct
10 Correct 268 ms 5108 KB Output is correct
11 Correct 142 ms 4956 KB Output is correct
12 Correct 80 ms 5112 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 175020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 263 ms 5140 KB Output is correct
8 Correct 66 ms 5144 KB Output is correct
9 Correct 66 ms 5112 KB Output is correct
10 Correct 268 ms 5108 KB Output is correct
11 Correct 142 ms 4956 KB Output is correct
12 Correct 80 ms 5112 KB Output is correct
13 Incorrect 98 ms 175020 KB Output isn't correct
14 Halted 0 ms 0 KB -