oj.uz

Submission #960928

# Submission time Handle Problem Language Result Execution time Memory
960928 2024-04-11T08:59:48 Z Ghetto Chase (CEOI17_chase) C++17
30 / 100
 571 ms 100692 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using lint = long long;
const int MAX_N = 1e5 + 5, MAX_K = 1e2 + 5;

int n, k;
lint val[MAX_N];
vector<int> adj[MAX_N], adj_ind[MAX_N]; // adj_ind[u][i] = ind of adj list u is for adj[u][i]

int par[MAX_N];
vector<int> children[MAX_N];
int child_ind[MAX_N];

int n_inds, ind[MAX_N], rev_ind[MAX_N];
void dfs(int u) {
    ind[u] = ++n_inds;
    rev_ind[ind[u]] = u;
    for (int v : adj[u]) {
        if (ind[v]) continue;
        par[v] = u;
        children[u].push_back(v);
        child_ind[v] = children[u].size() - 1;
        dfs(v);
    }
}

lint val_sum[MAX_N];

void precomp() {
    dfs(1);

    for (int i = 1; i <= n; i++)
        for (int j : adj[i]) val_sum[i] += val[j];
}

lint dp1[MAX_N][MAX_K];

int main() {
    // freopen("chase.in", "r", stdin);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    precomp();

    for (int c = 1; c <= k; c++) {
        for (int i = n; i >= 1; i--) {
            int u = rev_ind[i];

            lint leave = 0;
            for (int v : children[u]) leave = max(leave, dp1[v][c]);

            lint take = 0; 
            for (int v : children[u]) take = max(take, dp1[v][c - 1]);
            take += val_sum[u] - val[par[u]];

            dp1[u][c] = max(take, leave);
        }
    }

    cout << dp1[1][k] << endl;  
    
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 100692 KB Output is correct
2 Correct 341 ms 100480 KB Output is correct
3 Correct 251 ms 97076 KB Output is correct
4 Correct 107 ms 99512 KB Output is correct
5 Correct 571 ms 99820 KB Output is correct
6 Correct 461 ms 99564 KB Output is correct
7 Correct 502 ms 99968 KB Output is correct

Subtask #4
0 / 30.0

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