Submission #676815

#	Time	Username	Problem	Language	Result	Execution time	Memory
676815		peteza	Paprike (COI18_paprike)	C++14	100 / 100	113 ms	19564 KiB

paprike

#include <bits/stdc++.h>
using namespace std;

int n, k, a, b;
int val[100005];
vector<int> vec[100005];
int DP[100005]; //numbers of scoville taken

int dfs(int cn, int par = -1) {
    //returns minimum cut to make this tree
    if(vec[cn].size() == 1 && vec[cn][0] == par) {
        DP[cn] = val[cn];
        return 0;
    } //is a leaf node!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1
    int sum = 0, scovavail = k-val[cn];
    vector<int> sco;
    for(int e:vec[cn]) {
        if(e == par) continue;
        sum += dfs(e, cn);
        sco.push_back(DP[e]);
    }
    sort(sco.begin(), sco.end());
    //for(int e:sco) cout << e << ", "; cout << '\n';
    int i;
    for(i=0;i<sco.size() && scovavail >= sco[i];i++)scovavail -= sco[i];//cout << "Scoville available of " << i << "-> "<<sco[i] << '\n';
    //cout << "total scov = " << scovavail << '\n';
    DP[cn] = k-scovavail;
    //cout << cn << " -> " << sum << " + " << sco.size()-i << '\n';
    //cout << "--->" << DP[cn] << '\n';
    return sum+=sco.size()-i;
}

int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> val[i];
    for(int i=1;i<n;i++) {
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    cout << dfs(1);
}

Compilation message (stderr)

paprike.cpp: In function 'int dfs(int, int)':
paprike.cpp:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(i=0;i<sco.size() && scovavail >= sco[i];i++)scovavail -= sco[i];//cout << "Scoville available of " << i << "-> "<<sco[i] << '\n';
      |             ~^~~~~~~~~~~

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