Submission #206513

#	Time	Username	Problem	Language	Result	Execution time	Memory
206513		algorithm16	Paprike (COI18_paprike)	C++14	100 / 100	202 ms	25336 KiB

paprike

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long int llint;
llint arr[100005],sum[100005],n,k;
vector <int> v[100005];
llint dfs(int x,int par) {
	llint ret=arr[x];
	for(int i=0;i<v[x].size();i++) {
		if(v[x][i]==par) continue;
		ret+=dfs(v[x][i],x);
	}
	sum[x]=ret;
	return ret;
}
int rek(int x,int par) {
	int ret=0;
	sum[x]=arr[x];
	multiset <llint> s;
	for(int i=0;i<v[x].size();i++) {
		if(v[x][i]==par) continue;
		ret+=rek(v[x][i],x);
		sum[x]+=sum[v[x][i]];
		s.insert(sum[v[x][i]]);
		//if(x==5) cout << sum[v[x][i]] << "\n";
	}
	//cout << sum[x] << " " << ret << "\n"; 
	while(sum[x]>k) {
		multiset <llint>::iterator it=s.end();
		it--;
		//if(x==5) cout << distance(s.begin(),it) << " " << (*it) << " " << (*s.begin()) << "\n";
		ret+=1;
		sum[x]-=(*it);
		s.erase(it);
	}
	//if(x==5) cout << x << " " << sum[x] << " " << ret << "\n\n";
	return ret;
}
int main()
{
	cin >> n >> k;
	for(int i=0;i<n;i++) {
		cin >> arr[i];
	}
	for(int i=0;i<n-1;i++) {
		int a,b;
		cin >> a >> b;
		v[a-1].push_back(b-1);
		v[b-1].push_back(a-1);
	}
	dfs(0,-1);
	cout << rek(0,-1);
	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'llint dfs(int, int)':
paprike.cpp:11:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
paprike.cpp: In function 'int rek(int, int)':
paprike.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~

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