Submission #312458

#	Time	Username	Problem	Language	Result	Execution time	Memory
312458		colazcy	Paprike (COI18_paprike)	C++17	100 / 100	64 ms	15992 KiB

paprike

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 100;
inline int read(){
	int x = 0;char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = x * 10 + c - '0',c = getchar();
	return x;
}
int n,k,ans,val[maxn];
vector<int> G[maxn];
inline void addedge(int u,int v){G[u].push_back(v);} 
inline int dfs(int u,int faz = -1){
	int res = val[u];
	vector<int> vec;
	for(int i = 0;i < G[u].size();i++){
		int v = G[u][i];
		if(v == faz)continue;
		vec.push_back(dfs(v,u));
	}
	sort(vec.begin(),vec.end(),[](int a,int b){return a < b;}); 
	int i = 0;
	for(;i < vec.size() && res + vec[i] <= k;i++)res += vec[i];
	ans += vec.size() - i; 
	return res;
}
int main(){
//	freopen("paprike.in","r",stdin);
//	freopen("paprike.out","w",stdout);
	n = read(),k = read();
	for(int i = 1;i <= n;i++)val[i] = read();
	for(int u,v,i = 1;i < n;i++)
		u = read(),v = read(),addedge(u,v),addedge(v,u);
	dfs(1);
	printf("%d\n",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Compilation message (stderr)

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

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