Submission #123256

#	Time	Username	Problem	Language	Result	Execution time	Memory
123256		ioilolcom	Paprike (COI18_paprike)	C++14	100 / 100	79 ms	16376 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
const int N=1e5+7;
int n,k;
ll ans[N];
int cnt=0;
bool cmp(const int &a,const int &b){
	return ans[a]>ans[b];
}
vector<int> adj[N];
void dfs(int u,int p){
	if(p!=0) {
		adj[u].erase(find(adj[u].begin(),adj[u].end(),p));
	}
	for(int v:adj[u]) {
		dfs(v,u);
		ans[u]+=ans[v];
	}
	sort(adj[u].begin(),adj[u].end(),cmp);
	for(int a:adj[u]) {
		if(ans[u]>k) {
			ans[u]-=ans[a];
			cnt++;
		}
		else{
			break;
		}
	}
}
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	cin>>n>>k;
	for(int i=1; i<=n; i++) {
		cin>>ans[i];
	}

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

	dfs(1,0);
	cout<<cnt<<endl;
	return 0;
}

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