Submission #232877

#	Time	Username	Problem	Language	Result	Execution time	Memory
232877		shayan_p	Paprike (COI18_paprike)	C++14	100 / 100	77 ms	22136 KiB

paprike

// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int a[maxn], n, k, ans;
vector<int> v[maxn];

int dfs(int u, int par = -1){
    ll sum = a[u];
    vector<int> vec;
    for(int y : v[u]){
	if(y != par){
	    vec.PB(dfs(y, u));
	    sum+= vec.back();
	}
    }
    if(sum <= k)
	return sum;
    sort(vec.begin(), vec.end());
    while(sum > k){
	ans++;
	sum-= vec.back();
	vec.pop_back();
    }
    return sum;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    cin >> n >> k;
    for(int i = 1; i <= n; i++){
	cin >> a[i];
    }
    for(int i = 1; i <= n-1; i++){
	int a, b;
	cin >> a >> b;
	v[a].PB(b);
	v[b].PB(a);
    }
    dfs(1);
    return cout << ans << endl, 0;
}

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