Submission #1117583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117583		nasir_bashirov	Paprike (COI18_paprike)	C++11	100 / 100	80 ms	18384 KiB

paprike

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define int long long

const int sz = 1e5 + 5;
int n, k, x, y, res, a[sz], dp[sz];
vi g[sz];

void dfs(int node, int par){
    dp[node] = a[node];
    vi v;
    for(int i : g[node]){
        if(i == par)    continue;
        dfs(i, node);
        dp[node] += dp[i];
        v.push_back(dp[i]);
    }
    sort(all(v));
    while(dp[node] > k){
        // cout << dp[node] << endl;
        dp[node] -= v.back();
        v.pop_back();
        res++;
    }
}

void fmain(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i < n; i++){
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 1);
    cout << res;
}
 
signed main(){
    int tmr = 1;
    // cin >> tmr;
    while(tmr--){
        fmain();
    }
}

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