oj.uz

Submission #571770

# Submission time Handle Problem Language Result Execution time Memory
571770 2022-06-02T16:55:22 Z piOOE Chase (CEOI17_chase) C++17
40 / 100
 88 ms 10444 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const int N = 100001;
const ll infL = 3e18;

vector<int> g[N];
int n, k;
ll p[N], ans = 0;

multiset<ll> st;

ll sum_set = 0;

void dfs(int v, int par) {
    ll sum = 0;
    for (int to : g[v]) {
        if (to != par) {
            sum += p[to];
        }
    }
    bool add = false;
    ll del = -1;
    if (sz(st) < k) {
        st.insert(sum);
        sum_set += sum;
        add = true;
    } else {
        assert(!st.empty());
        if (*st.begin() < sum) {
            del = *st.begin();
            sum_set -= del;
            st.erase(st.begin());
            add = true;
            sum_set += sum;
            st.insert(sum);
        }
    }
    ans = max(ans, sum_set);
    for (int to: g[v]) {
        if (to != par) {
            dfs(to, v);
        }
    }
    if (add) {
        sum_set -= sum;
        st.extract(sum);
    }
    if (del != -1) {
        sum_set += del;
        st.insert(del);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    if (k == 0) {
        cout << 0;
        return 0;
    }
    if (n <= 1000) {
        for (int s = 0; s < n; ++s) {
            dfs(s, -1);
        }
        cout << ans;
    } else {
        dfs(0, -1);
    }
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 88 ms 2748 KB Output is correct
8 Correct 21 ms 2796 KB Output is correct
9 Correct 42 ms 2656 KB Output is correct
10 Correct 83 ms 2708 KB Output is correct
11 Correct 81 ms 2736 KB Output is correct
12 Correct 56 ms 2716 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 10444 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 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 88 ms 2748 KB Output is correct
8 Correct 21 ms 2796 KB Output is correct
9 Correct 42 ms 2656 KB Output is correct
10 Correct 83 ms 2708 KB Output is correct
11 Correct 81 ms 2736 KB Output is correct
12 Correct 56 ms 2716 KB Output is correct
13 Incorrect 43 ms 10444 KB Output isn't correct
14 Halted 0 ms 0 KB -