Submission #1025827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025827		vjudge1	Paprike (COI18_paprike)	C++17	24 / 100	41 ms	19176 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

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;
}

int 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: 0 / 27
• Subtask 4: 0 / 49