Submission #88720

#	Time	Username	Problem	Language	Result	Execution time	Memory
88720		igzi	Paprike (COI18_paprike)	C++17	100 / 100	80 ms	44556 KiB

paprike

#include <bits/stdc++.h>
#define maxN 100005

using namespace std;

vector <int> adj[maxN];
bool visited[maxN];
int ans[maxN],dp[maxN],n,k,h[maxN],i,a,b;

void dfs(int n){
vector <int> v;
ans[n]=0;
dp[n]=h[n];
visited[n]=true;
for(int i=0;i<adj[n].size();i++){
    if(!visited[adj[n][i]]){
       dfs(adj[n][i]);
       ans[n]+=ans[adj[n][i]];
       v.push_back(dp[adj[n][i]]);
    }
}
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++){
    if(dp[n]+v[i]>k) ans[n]++;
    else{
        dp[n]+=v[i];
    }
}
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin>>n>>k;
    for(i=0;i<n;i++){
        cin>>h[i];
    }
    for(i=0;i<n-1;i++){
        cin>>a>>b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(0);
    cout<<ans[0]<<endl;
    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(int)':
paprike.cpp:15:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
paprike.cpp:23:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<v.size();i++){
             ~^~~~~~~~~

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