제출 #571567

#제출 시각아이디문제언어결과실행 시간메모리
571567tekiPaprike (COI18_paprike)C++11
0 / 100
40 ms16324 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 sajz[nsize]; vector<ll> pat[nsize]; ll vred[nsize]; 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, ll parent) { ll bris = pat[pos].size()-1; for (auto it:pat[pos]) { if (it == parent) continue; dfs(it,pos); } sort(pat[pos].begin(),pat[pos].end()); for (auto it2:pat[pos]) { if (it2 == parent) continue; auto it = sajz[it2]; 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); } for (ll i = 0; i<n; i++) sajz[i] = vred[i]; dfs(0,-1); 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...