Submission #1293790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293790		Choco	Paprike (COI18_paprike)	C++17	100 / 100	37 ms	25452 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define ll long long
#define fori(i,j,k) for(ll i=j; i<=k;i++)
#define study ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define all(s) s.begin(),s.end()
#define ins insert
#define ss second
#define ff first
ll sz=2e5+10;
ll INF=1e12;
ll mod=1e9+7;
ll n,k;
vector<ll>subt(sz,-1),a(sz,-1),check(sz,0);
vector<vector<ll>>g(sz);
ll ans=0;
void dfs(ll t,ll par=-1){
    check[t]=1;
    subt[t]=a[t];
    priority_queue<ll>so;
    for(auto x: g[t]){
        if(x==par)
        continue;
        dfs(x,t);
        subt[t]+=subt[x];
        so.push(subt[x]);
    }
    while(subt[t]>k){
        ans++;
        subt[t]-=so.top();
        so.pop();
    }
}
void work(){
    cin>>n>>k;
    fori(i,1,n){
        cin>>a[i];
    }
    fori(i,1,n-1){
        ll a,b;
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs(1,-1);
    cout<<ans<<endl;
}
int main()
{
    study;
    ll t=1;
    //cin>>t;
    fori(i,1,t)
    work();
}
/*

*/

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