Submission #1142999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142999		ezzzay	Paprike (COI18_paprike)	C++20	100 / 100	83 ms	24648 KiB

paprike

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int h[N];
vector<int>v[N];
int n,k;
int sbtr[N];
int ans=0;
void dfs(int a,int p){
	sbtr[a]+=h[a];
	vector<int>vc;
	for(auto b:v[a]){
		if(b==p)continue;
		dfs(b,a);
		vc.pb(sbtr[b]);
	}
	sort(vc.begin(),vc.end(),greater<int>());
	while(vc.size()){
		if(sbtr[a]+vc.back()<=k){
			sbtr[a]+=vc.back();
			vc.pop_back();
		}
		else{
			ans+=vc.size();
			return;
		}
	}
}	
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>h[i];
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	dfs(1,0);
	cout<<ans;
}

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