Submission #70750

#	Time	Username	Problem	Language	Result	Execution time	Memory
70750		BartolM	Paprike (COI18_paprike)	C++11	24 / 100	224 ms	31592 KiB

paprike

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

using namespace std;

int n,k;

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

//vector<int>ljut;

void input(){
    cin>>n>>k;
    int 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);
    }
}

int sol=0;

int dfs(int x, int par){
    vector<int>ljut;
    for(int i=0;i<niz[x].size();i++){
        int node=niz[x][i];
        if(node==par)continue;
        ljut.push_back(dfs(node, x));
    }
    sort(ljut.begin(),ljut.end());
    int 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:19:16: warning: unused variable 'sum' [-Wunused-variable]
     int br,a,b,sum=0;
                ^~~
paprike.cpp: In function 'int dfs(int, int)':
paprike.cpp:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<niz[x].size();i++){
                 ~^~~~~~~~~~~~~~
paprike.cpp:46: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: 0 / 27
• Subtask 4: 0 / 49