Submission #746198

#	Time	Username	Problem	Language	Result	Execution time	Memory
746198		JellyTheOctopus	Paprike (COI18_paprike)	C++17	100 / 100	131 ms	22604 KiB

paprike

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

int N, K;
vector<int> adjList[100001];
int arr[100001];
int sum[100001];
int ans = 0;

void DFS(int node, int parent) {
	for (auto child: adjList[node]) {
		if (child != parent) {
			DFS(child, node);
		}
	}
	if ((int)adjList[node].size() == 1 && node != 1) {
		sum[node] = arr[node];
	}
	else {
		int cnt = arr[node];
		priority_queue<int> pq;
		for (auto child: adjList[node]) {
			if (child != parent) {
				pq.push(-sum[child]);
			}
		}
		int cuts = 0;
		while (!pq.empty()) {
			int w = -pq.top();
			cnt += w;
			pq.pop();
			if (cnt > K) {
				cnt -= w;
				cuts = (int)pq.size()+1;
				break;
			}
		}
		while (!pq.empty()) pq.pop();
		sum[node] = cnt;
		ans += cuts;
	}
}

int main() {
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < N-1; i++) {
		int u, v;
		cin >> u >> v;
		adjList[u].push_back(v);
		adjList[v].push_back(u);
	}
	DFS(1, -1);
	cout << ans << "\n";
}	

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