Submission #241826

#	Time	Username	Problem	Language	Result	Execution time	Memory
241826		marlicu	Paprike (COI18_paprike)	C++14	100 / 100	83 ms	24288 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;
int 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] += (ll)ljutina[x];
    if (suma[x] <= k) return koliko;

    sort(dodani.rbegin(), dodani.rend());

    int t = 0;
    while (t < dodani.size() && suma[x] > k) {
        suma[x] -= dodani[t];
        koliko++; t++;
    }

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

Compilation message (stderr)

paprike.cpp: In function 'int rezovi(int, int)':
paprike.cpp:35:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (t < dodani.size() && suma[x] > k) {
            ~~^~~~~~~~~~~~~~~

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