Submission #708918

#	Time	Username	Problem	Language	Result	Execution time	Memory
708918		JJAnawat	Paprike (COI18_paprike)	C++17	100 / 100	62 ms	18704 KiB

paprike

#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,k;
vector<int> g[100005];
int h[100005];
int dp[100005];

int dfs(int u,int p=1){
    if(u!=1&&g[u].size()==1){
        dp[u]=h[u];
        return 0;
    }
    int sum=0;
    vector<int> vec;
    for(auto v:g[u])
        if(v!=p){
            sum+=dfs(v,u);
            vec.push_back(dp[v]);
        }
    sort(vec.begin(),vec.end());
    int cnt=0;
    dp[u]=h[u];
    for(auto dpi:vec){
        if(dp[u]+dpi>k)
            break;
        dp[u]+=dpi;
        cnt++;
    }
    return sum+(vec.size()-cnt);
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for(int i=1;i<=n;i++)
        cin >> h[i];
    for(int i=1,x,y;i<n;i++){
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cout << dfs(1);
}

Compilation message (stderr)

paprike.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main(){
      | ^~~~

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