Submission #159751

#	Time	Username	Problem	Language	Result	Execution time	Memory
159751		DS007	Paprike (COI18_paprike)	C++14	100 / 100	82 ms	22868 KiB

paprike

#include <bits/stdc++.h>
using namespace std;

const int mn = 100000;
list<int> adj[mn];
long long h[mn];
int n, k, ans = 0;

long long dfs(int v, int p = -1) {
    vector<long long> val;
    long long sum = 0;

    for (int i : adj[v]) {
        if (i != p) {
            int temp = dfs(i, v);
            sum += temp;
            val.push_back(temp);
        }
    }

    sort(val.begin(), val.end(), greater<>());
    sum += h[v];

    int i = 0;
    while (sum > k) {
        ans++;
        sum -= val[i++];
    }

    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> h[i];

    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs(0);
    cout << ans << endl;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49