Submission #208347

#	Time	Username	Problem	Language	Result	Execution time	Memory
208347		MatesV13	Paprike (COI18_paprike)	C++11	100 / 100	93 ms	22648 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
long long n, k, h[100005], a, b, rez, ans;
vector<long long> c[100005];
vector<long long> l[100005];
long long lj[100005];
void dfs(int idx, int prev){
	if (lj[idx]) return;
	lj[idx]=h[idx];
	for (int i=0; i<c[idx].size(); i++){
		if (c[idx][i]==prev) continue;
		dfs(c[idx][i], idx); 
		l[idx].push_back(lj[c[idx][i]]);
	}
	sort(l[idx].begin(), l[idx].end());
	reverse(l[idx].begin(), l[idx].end());
	for (int i=0; i<l[idx].size(); i++)
		lj[idx]+=l[idx][i];
	for (int i=0; lj[idx]>k; i++){
		lj[idx]-=l[idx][i];
		rez++;
	}
	return;
}
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k; 
for (int i=1; i<=n; i++) 
	cin >> h[i];
for (int i=1; i<n; i++){
	cin >> a >> b;
	c[a].push_back(b);
	c[b].push_back(a);
}
dfs(1, -1);
cout << rez;
return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(int, int)':
paprike.cpp:10:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<c[idx].size(); i++){
                ~^~~~~~~~~~~~~~
paprike.cpp:17:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<l[idx].size(); i++)
                ~^~~~~~~~~~~~~~

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