제출 #1117579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117579		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	50 ms	22608 KiB

paprike

// evvelden elemisdim
// #pragma GCC optimize("Ofast,unroll-loops")

// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1e5+23, inf = 2e9, LG = 19,pr = 31;
int var[sze];
vector<int> graph[sze];

pair<int,int> dp[sze];
int k;
void dfs(int node,int par=-1){
    vector<int> lst;
    int sum=var[node];
    for(auto v:graph[node]){
        if(v!=par){
            dfs(v,node);
            dp[node].first+=dp[v].first;
            lst.pb(dp[v].second);
            sum+=dp[v].second;
        }
    }
    sort(all(lst));
    while(sum>k){
        sum-=lst.back();
        lst.pop_back();
        dp[node].first++;
    }
    dp[node].second = sum;
}

void fast(){
    int n;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>var[i];
    }
    for(int i =1;i<n;i++){
        int u,v;
        cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    dfs(1);
    putr(dp[1].first);
}

 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
    return 0;
}

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