Submission #96726

#	Time	Username	Problem	Language	Result	Execution time	Memory
96726		losmi247	Paprike (COI18_paprike)	C++14	100 / 100	113 ms	19064 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+43;
ll h[N],sz[N],n,k;
vector <ll> graf[N];
bool visited[N];
ll resi(ll a){
    visited[a] = 1;
    ll sol = 0;
    vector <ll> ch;
    for(auto f : graf[a]){
        if(visited[f]){
            continue;
        }
        sol += resi(f);
        sz[a] += sz[f];
        ch.push_back(sz[f]);
    }
    sz[a] += h[a];
    if(sz[a] <= k){
        return sol;
    }
    sort(ch.rbegin(),ch.rend());
    for(long i = 0; i < ch.size() && sz[a] > k; i++){
        sz[a] -= ch[i];
        sol++;
    }
    return sol;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    for(long i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(long i = 1; i < n; i++){
        ll u,v;
        cin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    cout << resi(1) << endl;
}

Compilation message (stderr)

paprike.cpp: In function 'll resi(ll)':
paprike.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long i = 0; i < ch.size() && sz[a] > k; i++){
                     ~~^~~~~~~~~~~

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