Submission #111098

#TimeUsernameProblemLanguageResultExecution timeMemory
111098rzbtPaprike (COI18_paprike)C++14
0 / 100
84 ms16844 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define F first #define S second #define all(x) x.begin(),x.end() #define MAXN 100005 typedef long long ll; using namespace std; int n,k; vector<int> niz[MAXN]; int spice[MAXN],otac[MAXN],stepen[MAXN]; int uk,res; set<pair<int,int> > listovi; void dfs(int t,int o){ int broj=0; otac[t]=o; for(auto x:niz[t]){ if(x==o)continue; broj++; dfs(x,t); } if(!broj)listovi.insert(make_pair(spice[t],t)); else stepen[t]=broj; } int main() { scanf("%d %d", &n, &k); for(int i=1;i<=n;i++){ scanf("%d", spice+i); uk+=spice[i]; } for(int i=1;i<n;i++){ int t1,t2; scanf("%d %d", &t1, &t2); niz[t1].pb(t2); niz[t2].pb(t1); } dfs(1,0); while(!listovi.empty()){ if(uk<=k){ res++; } int t=listovi.begin()->second; //printf(" %d %d %d\n",t,otac[t],spice[t]); if(t==1){ break; } listovi.erase(listovi.begin()); if(spice[otac[t]]+spice[t]>k){ res++; }else{ spice[otac[t]]+=spice[t]; } stepen[otac[t]]--; if(!stepen[otac[t]])listovi.insert(mp(spice[otac[t]],otac[t])); } printf("%d",res); return 0; }

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
paprike.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", spice+i);
         ~~~~~^~~~~~~~~~~~~~~
paprike.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...