Submission #1086489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086489		toast12	Paprike (COI18_paprike)	C++14	100 / 100	76 ms	20780 KiB

paprike

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

int k;

vector<vector<int>> adj;
vector<int> spice;

int ans = 0;

int dfs(int cur, int p) {
    if (adj[cur].size() == 1 && cur != p)
        return spice[cur];
    int s = spice[cur];
    priority_queue<int, vector<int>, greater<int>> pq;
    for (auto e : adj[cur]) {
        if (e != p) {
            int x = dfs(e, cur);
            pq.push(x);
        }
    }
    while (!pq.empty()) {
        if (s + pq.top() <= k) {
            s += pq.top();
            pq.pop();
        }
        else {
            ans += pq.size();
            break;
        }
    }
    return s;
}

int main() {
    int n;
    cin >> n >> k;
    adj.resize(n+1);
    spice.resize(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> spice[i];
    }
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1);
    cout << ans << '\n';
    return 0;
}

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