Submission #212923

#	Time	Username	Problem	Language	Result	Execution time	Memory
212923		Lukap	Paprike (COI18_paprike)	C++14	100 / 100	174 ms	17612 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

int n,k;
long long ljutina[100009];
vector<int> veze[100009];
long long rez;

 int dfs(int node, int par){
    vector<long long> v;
    long long zbroj = 0;
    for(int i = 0;i<veze[node].size();i++){
        if(veze[node][i]==par){
            continue;
        }
        v.push_back(dfs(veze[node][i],node));
    }
    sort(v.begin(),v.end());
    zbroj += ljutina[node];
    for(int i = 0;i<v.size();i++){
        zbroj += v[i];
    }
    while(zbroj > k){
        zbroj -= v[v.size()-1];
        v.erase(v.end()-1);
        rez++;
    }
    return zbroj;
 }


int main(){
    cin >> n >> k;
    for(int i = 0;i<n;i++){
        int a;
        cin >> a;
        ljutina[i] = a;
    }
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin >> a >> b;
        veze[a-1].push_back(b-1);
        veze[b-1].push_back(a-1);
    }
    rez = 0;
    dfs(0,0);
    cout << rez;
    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'int dfs(int, int)':
paprike.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<veze[node].size();i++){
                   ~^~~~~~~~~~~~~~~~~~
paprike.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<v.size();i++){
                   ~^~~~~~~~~

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