Submission #1025360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025360		delrey	Paprike (COI18_paprike)	C++14	13 / 100	69 ms	17236 KiB

paprike

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

long long n, k, h[100000], res, st[100000];
vector<long long> v[100000], c;

void dfs(int node, int parent) {
    //cout<<"node: "<<node<<" parent: "<<parent;
    st[node] = h[node];
    //c.clear();
    for(auto i : v[node]) {
        if(i == parent)
            continue;
        dfs(i, node);
        c.push_back(st[i]);
        st[node] += st[i];
    }
    //cout<<"st[node]: "<<st[node];
    if(st[node] > k) {
        sort(c.begin(), c.end());
        long long sum = h[node];
        for(auto i : c) {
            if(sum + i > k) {
                res++;
                //cout<<" +("<<node<<", "<<i<<") ";
                st[node] -= i;
            } else
                sum += i;
        }
        //cout<<" sum: "<<sum;
    }
    c.clear();
    //cout<<endl;
}

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

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