Submission #1133795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133795		mnbvcxz123	Paprike (COI18_paprike)	C++20	100 / 100	33 ms	18760 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, int> pi;
const int MAXN = 100005;

int n, k, a[MAXN];
vector<int> gph[MAXN];
int ans;

int dfs(int x, int p){
	vector<int> v;
	for(auto &i : gph[x]){
		if(i != p) v.push_back(dfs(i, x));
	}
	sort(v.begin(), v.end());
	int ret = a[x];
	for(int i=0; i<v.size(); i++){
		if(ret + v[i] > k){
			ans += v.size() - i;
			return ret;
		}
		ret += v[i];
	}
	return ret;
}
int main(){
	scanf("%d %d",&n,&k);
	for(int i=1; i<=n; i++) scanf("%d",&a[i]);
	for(int i=0; i<n-1; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	dfs(1, -1);
	cout << ans << endl;
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d %d",&n,&k);
      |         ~~~~~^~~~~~~~~~~~~~~
paprike.cpp:29:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         for(int i=1; i<=n; i++) scanf("%d",&a[i]);
      |                                 ~~~~~^~~~~~~~~~~~
paprike.cpp:32:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |                 scanf("%d %d",&s,&e);
      |                 ~~~~~^~~~~~~~~~~~~~~

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