Submission #77322

#	Time	Username	Problem	Language	Result	Execution time	Memory
77322		thebes	Paprike (COI18_paprike)	C++14	100 / 100	107 ms	46320 KiB

paprike

#include <bits/stdc++.h>
using namespace std;

const int MN = 1e5+5;
int n, k, i, arr[MN], x, y, ans, w[MN];
vector<int> vec[MN], adj[MN];

void solve(int n,int p){
	for(auto v : adj[n]){
		if(v == p) continue;
		solve(v, n);
		vec[n].push_back(w[v]);
	}
	w[n] = arr[n];
	if(vec[n].size()){
		sort(vec[n].begin(),vec[n].end());
		for(i=0;i<vec[n].size()&&w[n]+vec[n][i]<=k;i++)
			w[n] += vec[n][i];
		ans += vec[n].size()-i;
	}
}

int main(){
	for(scanf("%d%d",&n,&k),i=1;i<=n;i++)
		scanf("%d",&arr[i]);
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	solve(1, 0);
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void solve(int, int)':
paprike.cpp:17:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<vec[n].size()&&w[n]+vec[n][i]<=k;i++)
           ~^~~~~~~~~~~~~~
paprike.cpp: In function 'int main()':
paprike.cpp:24:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(scanf("%d%d",&n,&k),i=1;i<=n;i++)
      ~~~~~~~~~~~~~~~~~~~^~~~
paprike.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&arr[i]);
   ~~~~~^~~~~~~~~~~~~~
paprike.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~

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