Submission #797009

#	Time	Username	Problem	Language	Result	Execution time	Memory
797009		Trisanu_Das	Paprike (COI18_paprike)	C++17	100 / 100	92 ms	23488 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
 
const int MN = 1e5+5;
int n, k, i, arr[MN], u, v, ans, w[MN];
vector<int> vec[MN], adj[MN];
 
void dfs(int u,int p){
	for(auto v : adj[u]){
		if(v == p) continue;
		dfs(v, u);
		vec[u].push_back(w[v]);
	}
	w[u] = arr[u];
	if(vec[u].size()){
		sort(vec[u].begin() ,vec[u].end());
		for(i = 0; i < vec[u].size() && w[u] + vec[u][i] <= k;i++) w[u] += vec[u][i];
		ans += vec[u].size() - i;
	}
}
 
int main(){
	cin >> n >> k;
    for(int i = 1; i < n + 1; i++) cin >> arr[i];
	for(i = 1; i < n; i++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0);
	cout << ans << '\n';
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(int, int)':
paprike.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(i = 0; i < vec[u].size() && w[u] + vec[u][i] <= k;i++) w[u] += vec[u][i];
      |              ~~^~~~~~~~~~~~~~~

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