Submission #44546

#	Time	Username	Problem	Language	Result	Execution time	Memory
44546		iletavcioski	Paprike (COI18_paprike)	C++17	100 / 100	190 ms	44920 KiB

paprike

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<vector<int> > v;
int n;
ll k;
vector<ll> val;
int res=0;
ll dfs(int x,int prev)
{
    vector<ll> vk;
    ll brojac=val[x];
    for(int i=0;i<v[x].size();i++)
    {
        if(v[x][i]!=prev)
        {
            ll a=dfs(v[x][i],x);
            brojac+=a;
            vk.push_back(a);
        }
    }
    sort(vk.begin(),vk.end());
    reverse(vk.begin(),vk.end());
    int i=0;
    while(brojac>k&&i<vk.size())
    {
        res++;
        brojac-=vk[i];
        i++;
    }
    return brojac;
}
int main()
{
    cin>>n>>k;
    vector<int> vec;
    v.insert(v.begin(),n+1,vec);
    for(int i=0;i<n;i++)
    {
        ll a;
        cin>>a;
        val.push_back(a);
    }
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(0,-1);
    cout<<res<<endl;
    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'll dfs(int, int)':
paprike.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
paprike.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(brojac>k&&i<vk.size())
                     ~^~~~~~~~~~

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