Submission #528936

#	Time	Username	Problem	Language	Result	Execution time	Memory
528936		blue	Paprike (COI18_paprike)	C++17	100 / 100	66 ms	22232 KiB

paprike

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;

const int mx = 100'000;

int n;
ll k;

vi edge[1 + mx];

vll h(1 + mx);

vi cuts(1 + mx);
vll topct(1 + mx);

void dfs(int u, int p)
{
	vll lst;

	topct[u] = h[u];

	for(int v : edge[u])
	{
		if(v == p) continue;
		dfs(v, u);

		cuts[u] += cuts[v];
		topct[u] += topct[v];

		lst.push_back(topct[v]);
	}

	sort(lst.begin(), lst.end());

	while(topct[u] > k)
	{
		topct[u] -= lst.back();
		cuts[u]++;
		lst.pop_back();
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k;

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

	for(int e = 1; e <= n-1; e++)
	{
		int u, v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}

	dfs(1, 0);

	cout << cuts[1] << '\n';
}

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