Submission #87696

#	Time	Username	Problem	Language	Result	Execution time	Memory
87696		fasterthanyou	Paprike (COI18_paprike)	C++14	13 / 100	156 ms	33940 KiB

paprike

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define pb(x) push_back(x)

int n, res;
long long k, s[100015], d[100015];
vector<int> a[100015];

void dfs(int u, int p)
{
    int child = 0;
    for(int v : a[u])
        if(v != p) dfs(v, u), ++child;
    if (child<1)
    {
        d[u] = s[u];
        return;
    }
    long long sum = s[u];
    vector<long long> b;
    for(int v : a[u])
        if(v != p) b.pb(d[v]);
    sort(b.begin(), b.end());
    FOR(i,0,(int)b.size())
        if(sum+b[i]>k) res +=(int)b.size()-i;
            else sum += b[i];
    d[u] = sum;
}

int main()
{
    cin >> n >> k;
    FOR(i,1,n+1) cin >> s[i];
    FOR(i,0,n-1)
    {
        int u,v; cin >> u >> v;
        a[u].pb(v);
        a[v].pb(u);
    }
    dfs(1, -1);
    cout << res;
}

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