Submission #706443

#	Time	Username	Problem	Language	Result	Execution time	Memory
706443		mkupanovac	Paprike (COI18_paprike)	C++14	24 / 100	52 ms	20288 KiB

paprike

#include<bits/stdc++.h>
#define PB push_back

using namespace std;

const int MAXN = (1e5 + 10);

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

int dfs(int node, int par){
	int trz = 0, sol = 0;
	podstsum[node] += w[node];
	vector<int> 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());
	int 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++){
		int 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 'int dfs(int, int)':
paprike.cpp:14:6: warning: unused variable 'trz' [-Wunused-variable]
   14 |  int trz = 0, sol = 0;
      |      ^~~

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