Submission #102543

#	Time	Username	Problem	Language	Result	Execution time	Memory
102543		emaborevkovic	Paprike (COI18_paprike)	C++14	100 / 100	231 ms	24848 KiB

paprike

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n,k;

int p[100005];

vector <int> ls[100005];

vector <int> v[100005];

pair <int,int> func(int x, int parent) {
	pair <int,int> ret;
	ret.first = 0;
	ret.second = 0;
	for (int i=0;i<ls[x].size();i++) {
		if (ls[x][i] == parent) continue;
		pair <int,int> sada = func(ls[x][i], x);
		ret.first+=sada.first;
		v[x].push_back(sada.second);
	}
	int br = p[x];
	int makni = 0;
	sort(v[x].begin(), v[x].end());
	for (int i=0;i<v[x].size();i++) {
		if(br + v[x][i] <= k) {
			br += v[x][i];
			makni++;
		}
		else break;
	}
	ret.first += ls[x].size()-1-makni;
	ret.second = br;
	return ret;
}

int main() {
	cin >> n >> k;
	for (int i=0;i<n;i++) {
		cin >> p[i];
	}
	for (int i=0;i<n-1;i++) {
		int x,y;
		cin >> x >> y; x--; y--;
		ls[x].push_back(y);
		ls[y].push_back(x);
	}
	cout << func(0,0).first+1;
	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'std::pair<int, int> func(int, int)':
paprike.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<ls[x].size();i++) {
               ~^~~~~~~~~~~~~
paprike.cpp:28:16: 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