Submission #650634

#	Time	Username	Problem	Language	Result	Execution time	Memory
650634		ymm	Paprike (COI18_paprike)	C++17	100 / 100	60 ms	21076 KiB

paprike

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
vector<int> A[N];
ll h[N];
int n; ll k;

pll dfs(int v, int p)
{
	int ans = 1;
	vector<ll> vec;
	for (int u : A[v]) {
		if (u != p) {
			auto [x, y] = dfs(u, v);
			ans += x;
			vec.push_back(y);
		}
	}
	sort(vec.begin(), vec.end());
	ll sum = h[v];
	for (auto x : vec) {
		if (sum + x > k)
			break;
		sum += x;
		ans -= 1;
	}
	return {ans, sum};
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> k;
	Loop (i,0,n)
		cin >> h[i];
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	cout << dfs(0, -1).first - 1 << '\n';
}

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