Submission #1117587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117587		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	98 ms	26220 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, k, a, b;
vector<ll> sp, dp;
vector<vector<int>> v;
int cnt = 0;
void dfs(int x, int p){
    set<vector<ll>> se;
    dp[x] = sp[x];
    for (auto el : v[x]){
        if (el != p){
            dfs(el, x);
            se.insert({dp[el], el});
            dp[x] += dp[el];
        }
    }
    while (dp[x] > k){
        dp[x] -= se.rbegin()->at(0);
        se.erase(*se.rbegin());
        cnt++;
    }
}
int main(){
    cin>>n>>k;
    sp.assign(n + 2, 0), dp.assign(n + 1, 0);
    v.assign(n + 1, vector<int>());
    for (int i = 1; i <= n; i++){
        cin>>sp[i];
    }
    for (int i = 0; i < n - 1; i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1, 0);
    cout<<cnt;
}

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