제출 #89971

#제출 시각아이디문제언어결과실행 시간메모리
89971vexPaprike (COI18_paprike)C++14
24 / 100
64 ms18304 KiB
#include <bits/stdc++.h> #define maxn 100005 #define pii pair<int,int> #define ljutina first #define brojSecenja second #define par second.second #define node second.first using namespace std; int n,k; int h[maxn]; vector<pair<pii,pii>>adj[maxn]; pii dp[maxn]; bool cmp(pair<pii,pii> ff,pair<pii,pii> ss) { if(ff.par==1)return true; if(ss.par==1)return false; return ff.first.ljutina<=ss.first.ljutina; } void dfs(int v,int p) { dp[v].ljutina=0; dp[v].brojSecenja=0; bool leaf=true; for(auto x:adj[v]) { int u=x.node; if(u==p) { x.par=1; continue; } dfs(u,v); leaf=false; } dp[v].ljutina=h[v]; if(leaf)return; int len=adj[v].size(); for(int i=0;i<len;i++) { int cv=adj[v][i].node; adj[v][i].first.ljutina=dp[cv].ljutina; adj[v][i].first.brojSecenja=dp[cv].brojSecenja; } sort(adj[v].begin(),adj[v].end(),cmp); /*cout<<v<<" "; for(auto x:adj[v]) { cout<<x.first.ljutina<<","<<x.first.brojSecenja<<","<<x.node<<","<<x.par<<" "; }cout<<endl;*/ int poc=0;if(p!=v)poc=1; for(int i=poc;i<len;i++) { int cv=adj[v][i].node; dp[v].brojSecenja+=dp[cv].brojSecenja; if(dp[v].ljutina+dp[cv].ljutina<=k)dp[v].ljutina+=dp[cv].ljutina; else dp[v].brojSecenja++; } } int main() { ios_base::sync_with_stdio(false); 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; adj[x].push_back({{0,0},{y,0}}); adj[y].push_back({{0,0},{x,0}}); } dfs(1,1); //for(int i=1;i<=n;i++)cout<<dp[i].ljutina<<","<<dp[i].brojSecenja<<" "; cout<<dp[1].brojSecenja<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...