Submission #706420

#	Time	Username	Problem	Language	Result	Execution time	Memory
706420		mdobric	Paprike (COI18_paprike)	C++11	100 / 100	121 ms	17476 KiB

paprike

#include <bits/stdc++.h>
using namespace std;

int n, k;
int h[100005];
int x[100005], y[100005];
vector <int> v[100005];
int zbr[100005];
int rez = 0;
int parent[100005];

void solve (int tr){
	vector <int> v2;
	for (int i = 0; i < v[tr].size(); i++){
		if (zbr[v[tr][i]] == -1){
			solve(v[tr][i]);
		}
		v2.push_back(zbr[v[tr][i]]);
	}
	sort(v2.begin(), v2.end());
	int suma = h[tr], ukp = 0;
	for (int i = 0; i < v2.size(); i++){
		if (suma + v2[i] <= k){
			suma = suma + v2[i];
			ukp++;
		}
		else{
			break;
		}
	}
	rez = rez + v2.size() - ukp;
	zbr[tr] = suma;
	//cout << tr << " " << rez << " " << zbr[tr] << endl;
	return;
}

int main (void){
	
	memset(zbr, -1, sizeof zbr);
	memset(parent, -1, sizeof parent);
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		cin >> h[i];
	}
	for (int i = 0; i < n - 1; i++){
		cin >> x[i] >> y[i];
		if (parent[x[i]] != -1){
			v[x[i]].push_back(y[i]);
			parent[y[i]] = 1;
		}
		else
		if (parent[y[i]] != -1){
			v[y[i]].push_back(x[i]);
			parent[x[i]] = 1;
		}
		else
		if (x[i] < y[i]){
			v[x[i]].push_back(y[i]);
			parent[y[i]] = 1;
		}
		else{
			v[y[i]].push_back(x[i]);
			parent[x[i]] = 1;
		}
	}
	for (int i = 1; i <= n; i++){
		if (v[i].size() == 0){
			zbr[i] = h[i];
		}
	}
	solve(1);
	cout << rez;
	
	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void solve(int)':
paprike.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for (int i = 0; i < v[tr].size(); i++){
      |                  ~~^~~~~~~~~~~~~~
paprike.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 0; i < v2.size(); i++){
      |                  ~~^~~~~~~~~~~

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