Submission #124593

#	Time	Username	Problem	Language	Result	Execution time	Memory
124593		Adhyyan1252	Paprike (COI18_paprike)	C++11	100 / 100	84 ms	18056 KiB

paprike

#include<bits/stdc++.h>

using namespace std;

#define int long long

int n, k;
vector<int> h;
vector<vector<int> > g;


vector<int> dpa, dpb;

pair<int, int> dfs(int cur, int par){
	vector<pair<int, int> > c;
	int sum = 0;
	for(int u: g[cur]){
		if(u == par) continue;
		c.push_back(dfs(u, cur));
		sum += c.back().second;
	}
	sort(c.begin(), c.end());
	int csum = h[cur];
	for(auto u: c){
		if(csum + u.first <= k){
			csum += u.first;
		}else{
			sum++;
		}
	}
	return {csum, sum};
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k;
	h.resize(n);
	for(int i = 0; i < n; i++){
		cin>>h[i];
	}
	
	
	g.resize(n);
	for(int i = 0; i < n-1; i++){
		int x, y; cin>>x>>y; x--, y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	cout<<dfs(0, -1).second<<endl;
}

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