Submission #390290

#	Time	Username	Problem	Language	Result	Execution time	Memory
390290		fadi57	Paprike (COI18_paprike)	C++14	100 / 100	139 ms	15964 KiB

paprike

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mx=1e5+10;
const int mod= 1e9+7 ;
const ll inf=1e9+5;
//***while there is life there is hope

int n,m,k;
int siz[mx];int ans;
vector<int> adj[mx];

int arr[mx];

int vis[mx];
int dfs(int node){
vis[node]=1;


 vector<int>v;
   for(auto it:adj[node]){
    if(vis[it]){continue;}
    v.push_back(dfs(it));
   }
int ret=arr[node];

sort(v.begin(),v.end());
for(auto it:v){


    if(ret+it<=k){
        ret+=it;
    }else{
    ans++;

    }
}
return ret;
 }

int main() {

cin>>n>>k;int sum2=0;
for(int i=1;i<=n;i++){
    cin>>arr[i];sum2+=arr[i];
}

for(int i=0;i<n-1;i++){
    int a,b;cin>>a>>b;


    adj[a].push_back(b);
    adj[b].push_back(a);

 }


dfs(1);

cout<<ans;


 }

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