Submission #967184

#	Time	Username	Problem	Language	Result	Execution time	Memory
967184		mdobric	Paprike (COI18_paprike)	C++11	100 / 100	41 ms	18816 KiB

paprike

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

const int maxn = 1e5 + 5;
int n, a[maxn], b[maxn], p[maxn];
long long h[maxn], k;
int dp[maxn];
long long ostatak[maxn];
vector <int> v[maxn];

void dfs (int x){
	for (int i = 0; i < v[x].size(); i++){
		if (p[x] != v[x][i]){
			p[v[x][i]] = x;
			dfs(v[x][i]);
		}
	}
}

int solve (int x){
	vector <long long> sve;
	for (int i = 0; i < v[x].size(); i++){
		if (p[x] != v[x][i]){
			solve(v[x][i]);
			dp[x] += dp[v[x][i]];
			sve.push_back(ostatak[v[x][i]]);
		}
	}
	sort(sve.begin(), sve.end());
	long long tr = h[x];
	for (int i = 0; i < sve.size(); i++){
		if (tr + sve[i] <= k){
			tr += sve[i];
		}
		else{
			dp[x]++;
		}
	}
	ostatak[x] = tr;
	//cout << x << " : " << dp[x] << " " << ostatak[x] << endl;
	//cout << sve.size() << endl << endl;
	return dp[x];
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		cin >> h[i];
	}
	for (int i = 0; i < n - 1; i++){
		cin >> a[i] >> b[i];
		v[a[i]].push_back(b[i]);
		v[b[i]].push_back(a[i]);
	}
	dfs(1);
	cout << solve(1) << "\n";
	
	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(int)':
paprike.cpp:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for (int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
paprike.cpp: In function 'int solve(int)':
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 < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
paprike.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i = 0; i < sve.size(); i++){
      |                  ~~^~~~~~~~~~~~

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