Submission #230019

#	Time	Username	Problem	Language	Result	Execution time	Memory
230019		dolphingarlic	Paprike (COI18_paprike)	C++14	100 / 100	69 ms	19240 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<ll> 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