Submission #71637

#	Time	Username	Problem	Language	Result	Execution time	Memory
71637		miljenko_jabucica	Paprike (COI18_paprike)	C++14	100 / 100	243 ms	17132 KiB

paprike

#include<bits/stdc++.h>

using namespace std;
int n, k;
long long niz [100005];
vector <int> v[100005];
int a[100005];
int b[100005];
int rez = 0;
int dfs(int x, int par){
    long long sum = 0;
    vector<long long> lj_djeca;
    if (v[x].size() == 1 && x != 1)return niz[x-1];
    for (int i = 0; i < v[x].size(); ++i){
        int node = v[x][i];
        if (node == par)continue;
        long long sum2 = dfs(node, x);
        lj_djeca.push_back(sum2);
        sum += sum2;
        ///cout <<node <<" " <<sum[node] <<endl;
    }
    sum += niz[x-1];
    sort(lj_djeca.begin(), lj_djeca.end());
    ///cout <<"x -> " <<x <<endl;
    ///for (int i = 0; i < lj_djeca.size(); ++i)cout <<lj_djeca[i] <<" ";
    ///cout <<endl;
    int i = 0;
    while (sum>k){
        sum -= lj_djeca[lj_djeca.size()-1];
        lj_djeca.pop_back();
        ++rez;
    }
    return sum;
}

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

Compilation message (stderr)

paprike.cpp: In function 'int dfs(int, int)':
paprike.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v[x].size(); ++i){
                     ~~^~~~~~~~~~~~~
paprike.cpp:27:9: warning: unused variable 'i' [-Wunused-variable]
     int i = 0;
         ^

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