Submission #144807

#	Time	Username	Problem	Language	Result	Execution time	Memory
144807		emilem	Paprike (COI18_paprike)	C++14	100 / 100	214 ms	18536 KiB

paprike

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int n, k;
vector<int> h, toLeaf;
vector< vector<int> > nei;
vector<int> ans, val;

void Dfs(int v, int par)
{
	vector<int> vals;
	val[v] = h[v];
	for (int i = 0; i < nei[v].size(); ++i)
	{
		int to = nei[v][i];
		if (to == par) continue;
		Dfs(to, v);
		ans[v] += ans[to];
		vals.push_back(val[to]);
	}
	sort(vals.begin(), vals.end());
	ans[v] += vals.size();
	for (int i = 0; i < vals.size(); ++i)
		if (val[v] + vals[i] <= k)
		{
			val[v] += vals[i];
			--ans[v];
		}
}
int main()
{
	cin >> n >> k;
	h.resize(n + 1); nei.resize(n + 1); ans.resize(n + 1); val.resize(n + 1);
	for (int i = 1; i <= n; ++i)
		cin >> h[i];
	for (int i = 1; i < n; ++i)
	{
		int u, v;
		cin >> u >> v;
		nei[u].push_back(v);
		nei[v].push_back(u);
	}
	Dfs(1, -1);
	cout << ans[1] << endl;

	char I;
	cin >> I;
}

Compilation message (stderr)

paprike.cpp: In function 'void Dfs(int, int)':
paprike.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[v].size(); ++i)
                  ~~^~~~~~~~~~~~~~~
paprike.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vals.size(); ++i)
                  ~~^~~~~~~~~~~~~

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