Submission #706445

#	Time	Username	Problem	Language	Result	Execution time	Memory
706445		mkupanovac	Paprike (COI18_paprike)	C++14	100 / 100	80 ms	18420 KiB

paprike

#include<bits/stdc++.h>
#define PB push_back
#define ll long long
using namespace std;

const int MAXN = (1e5 + 10);

ll n, k;
ll w[MAXN];
ll podstsum[MAXN];
vector<ll> graph[MAXN];

ll dfs(ll node, ll par){
	ll trz = 0, sol = 0;
	podstsum[node] += w[node];
	vector<ll> djeca;
	for (auto x: graph[node]){
		if (x == par) continue;
		sol += dfs(x, node);
		podstsum[node] += podstsum[x];
		djeca.PB(podstsum[x]);
	}

	if (podstsum[node] <= k){
		return sol;
	}
	
	sort(djeca.begin(), djeca.end());
	ll tr = djeca.size() - 1;
	while (podstsum[node] > k){

		podstsum[node] -= djeca[tr];
		tr--;
		sol++;
	}
	
	
	return sol;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> k;
	
	for (int i = 0; i < n; i++)
		cin >> w[i + 1];
		
	for (int i = 0; i < n - 1; i++){
		ll a, b;
		cin >> a >> b;
		graph[a].PB(b);
		graph[b].PB(a);
	}
	
	cout << dfs(1, 0) << "\n";
	
	
	
	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'long long int dfs(long long int, long long int)':
paprike.cpp:14:5: warning: unused variable 'trz' [-Wunused-variable]
   14 |  ll trz = 0, sol = 0;
      |     ^~~

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