Submission #241824

#	Time	Username	Problem	Language	Result	Execution time	Memory
241824		marlicu	Paprike (COI18_paprike)	C++14	51 / 100	1093 ms	23096 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define X first
#define Y second

typedef long long ll;

const int MAXN = 3e5 + 5;

int n, k;
ll ljutina[MAXN];
vector <int> veze[MAXN];
ll suma[MAXN];

int rezovi(int x, int px) {
    int koliko = 0;
    vector <ll> dodani;

    for (auto nx : veze[x]) {
        if (nx == px) continue;
        koliko += rezovi(nx, x);
        suma[x] += suma[nx];
        dodani.push_back(suma[nx]);
    }

    suma[x] += ljutina[x];
    if (suma[x] <= k) return koliko;

    sort(dodani.begin(), dodani.end());
    reverse(dodani.begin(), dodani.end());

    while (suma[x] > k) {
        suma[x] -= dodani[0];
        dodani.erase(dodani.begin());
        koliko++;
    }

    return koliko;
}

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

    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> ljutina[i];

    int a, b;
    for (int i = 1; i < n; i++) {
        cin >> a >> b;
        --a; --b;
        veze[a].pb(b);
        veze[b].pb(a);
    }

    cout << rezovi(0, -1) << '\n';

    return 0;
}

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