Submission #1117943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117943		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	40 ms	23272 KiB

paprike

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

#define ll long long
#define FORI(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, n) for(ll i = 1; i <= n; i++)
typedef vector<ll> vl; 
typedef set<ll> setl;
#define ff first
#define ss second    
#define all(v) v.begin(), v.end() 
#define pll pair<ll, ll> 
#define db double
#define nll cout << "\n"
#define nl "\n"
#define sync ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

struct DSU{
    vl par;
    int components;
    DSU(int sz = 1){
        components = sz;
        par.resize(sz + 5, -1);
    }
    int Find(int u){
        if(par[u] < 0)   return u;
        else    return par[u] = Find(par[u]);
    }
    bool Union(int u, int v){
        u = Find(u), v = Find(v);
        if(u != v){
            if(par[u] < par[v]){
                swap(u, v);
            }
            par[u] += par[v];
            par[v] = u;
            components--;
            return true;
        }
        else{
            return false;
        }
    }
};
const ll MOD =  1e9 + 7;
const int MAX = 2e5 + 5;

ll n, m, k, res;ll a[MAX];
vector < ll > g[MAX];
ll dp[MAX];
ll used[MAX];
void dfs(ll v){
    used[v] = 1;
    dp[v] = a[v];
    vl cur;
    for(auto i : g[v]){
        if(!used[i]){    
            dfs(i);
            dp[v] += dp[i];
            cur.push_back(dp[i]);
        }
    }
    sort(all(cur));
    while(dp[v] > k){
        res++;
        dp[v] -= cur.back();
        cur.pop_back();
    }
}
void solve(){
    cin >> n >> k;
    FOR(i, n)cin >> a[i];
    ll u, v;
    FOR(i, n - 1){
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    cout << res;
}
signed main(){  
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    sync;
    ll t = 1;
    // cin >> t;
    FOR(i, t){
        // cout << "Case #" << i << ": ";
        solve();
    }
}

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