Submission #241013

#	Time	Username	Problem	Language	Result	Execution time	Memory
241013		topovik	Paprike (COI18_paprike)	C++14	100 / 100	182 ms	16132 KiB

paprike

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define INF 1000000000
#define N (long)1e6

using namespace std;

typedef long long ll;
typedef long double ld;

vector <vector <ll> > a;

ll n,k;
ll b[N];
ll ans;

ll Rec(ll x, ll y)
{
    vector <ll> c;
    ll sum=b[x];
    for (ll i=0; i<a[x].size(); i++)
        if (a[x][i]!=y) c.pb(Rec(a[x][i],x)),sum+=c.back();
    sort(c.begin(),c.end());
    reverse(c.begin(),c.end());
    for (ll i=0; sum>k; i++) sum-=c[i],ans++;
    return sum;
}

int main()
{
    cin>>n>>k;
    for (ll i=0; i<n; i++) cin>>b[i];
    a.resize(n);
    for (ll i=0; i<n-1; i++)
    {
        ll x,y;
        cin>>x>>y;
        a[--x].pb(--y);
        a[y].pb(x);
    }
    Rec(0,0);
    cout<<ans;
}

Compilation message (stderr)

paprike.cpp: In function 'll Rec(ll, ll)':
paprike.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll i=0; i<a[x].size(); i++)
                  ~^~~~~~~~~~~~

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