Submission #391116

#	Time	Username	Problem	Language	Result	Execution time	Memory
391116		asbsfds	Paprike (COI18_paprike)	C++14	100 / 100	76 ms	21824 KiB

paprike

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n;
llint k;
llint niz[maxn];
vector< int > graph[maxn];

int sol;
int solve(int x, int parr) {
	vector< llint > v;
	
	llint sum = niz[x];
	for (int i = 0; i < graph[x].size(); i++) {
		int tren = graph[x][i];
		if (tren != parr) {
			llint ax = solve(tren, x);
			v.push_back(ax);
			sum += ax;
		}
	}
	
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	
	int ptr = 0;
	while (sum > k) {
		sol++;
		sum -= v[ptr++];
	}
	return sum;
}

int main() {
	scanf("%d%lld", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%lld", niz+i);
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	solve(1, -1);
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'int solve(int, int)':
paprike.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
paprike.cpp: In function 'int main()':
paprike.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  scanf("%d%lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
paprike.cpp:48:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  for (int i = 1; i <= n; i++) scanf("%lld", niz+i);
      |                               ~~~~~^~~~~~~~~~~~~~~
paprike.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

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