Submission #1026746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026746		kkkkkkkk	Paprike (COI18_paprike)	C++14	100 / 100	40 ms	21936 KiB

paprike

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int n, k;
int spicy[100005];
vector<int> G[100005];
int cuts[100005];
 
int dfs(int teme, int parent) {
    vector<int> subtree_spice;
    int vk_spice=spicy[teme];
    for (auto next:G[teme]) {
        if (next==parent) continue;
        int klk_spice=dfs(next, teme);
        subtree_spice.push_back(klk_spice);
        vk_spice+=klk_spice;
        cuts[teme]+=cuts[next];
    }
    if (vk_spice<=k) return vk_spice;
    sort(subtree_spice.begin(), subtree_spice.end());
    int zbir=spicy[teme];
    for (auto x:subtree_spice) {
        if (zbir+x<=k) zbir+=x;
        else cuts[teme]++;
    }
    return zbir;
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i=1;i<=n;i++)
        cin >> spicy[i];
    for (int i=0;i<n-1;i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1, 0);
    cout << cuts[1];
 
    return 0;
}

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