Submission #230018

#	Time	Username	Problem	Language	Result	Execution time	Memory
230018		dolphingarlic	Paprike (COI18_paprike)	C++14	100 / 100	73 ms	22776 KiB

paprike

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, k;
ll a[100001];
vector<int> graph[100001];

int dfs(int node = 1, int parent = 0) {
    priority_queue<int> pq;
    int ans = 0;
    for (int i : graph[node]) if (i != parent) {
        ans += dfs(i, node);
        pq.push(a[i]);
        a[node] += a[i];
    }
    while (a[node] > k) {
        ans++;
        a[node] -= pq.top();
        pq.pop();
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    FOR(i, 1, n + 1) cin >> a[i];
    FOR(i, 1, n) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    cout << dfs();
    return 0;
}

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