Submission #571545

#TimeUsernameProblemLanguageResultExecution timeMemory
571545tekiPaprike (COI18_paprike)C++11
0 / 100
58 ms16964 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 int nsize = 100001; int n,m,q; int parent[nsize]; int sajz[nsize]; vector<int> pat[nsize]; bool vis[nsize]; int vred[nsize]; void dfsConst(int pos, int parnt) { if (vis[pos]) return; vis[pos] = true; parent[pos] = parnt; for (auto it:pat[pos]) dfsConst(it,pos); } bool custComp(int a, int b) { if (sajz[a] == sajz[b]) return a < b; return sajz[a] > sajz[b]; } int res = 1; void dfs(int pos) { vector<int> deca; int 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); cin>>n>>q; m = n-1; for (int i = 0; i<n; i++) cin>>vred[i]; for (int i = 0; i<m; i++) { int a,b; cin>>a>>b; a--; b--; pat[a].pb(b); pat[b].pb(a); } MS(vis,0); for (int i = 0; i<n; i++) sajz[i] = vred[i]; dfsConst(0,0); dfs(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...