Submission #571547

#TimeUsernameProblemLanguageResultExecution timeMemory
571547tekiPaprike (COI18_paprike)C++11
0 / 100
42 ms17596 KiB
#include <bits/stdc++.h> typedef long long ll; #define pb push_back #define MS(x,y) memset((x),(y),sizeof((x))) #define MN 1000000001 using namespace std; const ll nsize = 100001; ll n,m,q; ll parent[nsize]; ll sajz[nsize]; vector<ll> pat[nsize]; bool vis[nsize]; ll vred[nsize]; void dfsConst(ll pos, ll parnt) { if (vis[pos]) return; vis[pos] = true; parent[pos] = parnt; for (auto it:pat[pos]) dfsConst(it,pos); } bool custComp(ll a, ll b) { if (sajz[a] == sajz[b]) return a < b; return sajz[a] > sajz[b]; } ll res = 1; void dfs(ll pos) { vector<ll> deca; ll bris = pat[pos].size()-1; for (auto it:pat[pos]) { if (it == parent[pos]) continue; dfs(it); deca.pb(sajz[it]); } sort(deca.begin(),deca.end()); for (auto it:deca) { if (sajz[pos]+it <= q) { sajz[pos] += it; bris--; } else { res += bris; return; } } } int main() { #if LOCAL_DEBUG fstream cin("in.txt"); #endif ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll zbir = 0; cin>>n>>q; m = n-1; for (ll i = 0; i<n; i++) cin>>vred[i]; for (ll i = 0; i<n; i++) zbir += vred[i]; for (ll i = 0; i<m; i++) { ll a,b; cin>>a>>b; a--; b--; pat[a].pb(b); pat[b].pb(a); } MS(vis,0); for (ll i = 0; i<n; i++) sajz[i] = vred[i]; dfsConst(0,0); dfs(0); if (zbir <= q) { cout<<0<<endl; return 0; } cout<<res<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...