Submission #234556

#	Time	Username	Problem	Language	Result	Execution time	Memory
234556		Saboon	Paprike (COI18_paprike)	C++14	100 / 100	74 ms	17656 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<long double> point;
 
const int maxn = 100000 + 10;
const int maxm = 50 + 5;

int k, cnt;
int a[maxn];
vector<int> t[maxn];

void dfs(int v, int par = -1){
	cnt ++;
	vector<int> A;
	for (auto u : t[v])
		if (u != par)
			dfs(u, v), A.push_back(a[u]);
	sort(A.begin(), A.end());
	for (auto x : A)
		if (a[v] + x <= k)
			a[v] += x, cnt --;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n-1; i++){
		int v, u;
		cin >> v >> u;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	dfs(1);
	cout << cnt - 1 << endl;
}

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