Submission #640572

#	Time	Username	Problem	Language	Result	Execution time	Memory
640572		hotboy2703	Paprike (COI18_paprike)	C++14	24 / 100	58 ms	17892 KiB

paprike

#include<bits/stdc++.h>
using namespace std;
int n,k;
int h[100100];
vector <int> g[100100];
pair <int,int> dp[100100];
void dfs(int u,int pre){
    for (auto v:g[u]){
        if (v == pre)continue;
        dfs(v,u);
    }
    dp[u] = {0,h[u]};
    vector <int> all;
    for (auto v:g[u]){
        if (v == pre)continue;
        dp[u].first += dp[v].first;
        dp[u].second += dp[v].second;
        all.push_back(dp[v].second);
    }
    sort(all.begin(),all.end(),greater <int> ());
    int cur = 0;
    while (dp[u].second > k){
        dp[u].second -= all[cur];
        cur++;
        dp[u].first++;
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>k;
    for (int i = 1;i <= n;i ++){
        cin>>h[i];
    }
    for (int i = 1;i < n;i ++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,1);
    cout<<dp[1].first<<'\n';
    return 0;
}

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