Submission #71758

#	Time	Username	Problem	Language	Result	Execution time	Memory
71758		fabjanm	Paprike (COI18_paprike)	C++98	100 / 100	244 ms	16376 KiB

paprike

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>

using namespace std;

int n,k;

typedef long long ll;

//vector<pair<int,int> >edge;
vector<ll> niz[100100];
vector<ll>ljutina;

//vector<int>ljut;

void input(){
    cin>>n>>k;
    ll br,a,b,sum=0;
    for(int i=0;i<n;i++){
        cin>>br;
        ljutina.push_back(br);
    }

    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        a--;
        b--;
        //edge.push_back(make_pair(a,b));
        niz[a].push_back(b);
        niz[b].push_back(a);
    }
}

ll sol=0;

int dfs(ll x, ll par){
    vector<ll>ljut;
    for(int i=0;i<niz[x].size();i++){
        ll node=niz[x][i];
        if(node==par)continue;
        ljut.push_back(dfs(node, x));
    }
    sort(ljut.begin(),ljut.end());
    ll zbr=ljutina[x];
    for(int i=0;i<ljut.size();i++)zbr+=ljut[i];
    for(int i=ljut.size()-1;i>=0;i--){
        if(zbr<=k)break;
        else{
            zbr-=ljut[i];
            sol++;
        }
    }

    return zbr;
}

int main(){
    input();
    dfs(0, -1);
    cout<<sol;



    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void input()':
paprike.cpp:21:15: warning: unused variable 'sum' [-Wunused-variable]
     ll br,a,b,sum=0;
               ^~~
paprike.cpp: In function 'int dfs(ll, ll)':
paprike.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<niz[x].size();i++){
                 ~^~~~~~~~~~~~~~
paprike.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ljut.size();i++)zbr+=ljut[i];
                 ~^~~~~~~~~~~~

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