Submission #1293799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293799		Gadir_2880	Paprike (COI18_paprike)	C++20	100 / 100	41 ms	21612 KiB

paprike

//The Rumbling starts here:
 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include<bits/stdc++.h>
using namespace std;
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define int long long
#define all(x) x.begin(),x.end() 
#define ai array<int,2>
#define vv vector
#define pb push_back
 
const int N=1e6+5;
const int mod=1e9+7;
const int inf=(1ll<<55)-1;
int n,k;

int a[N];
vector<int> g[N];
int res[N];

void dfs(int u,int p) {
  multiset<int> ve;
  for (int v : g[u]) {
    if (v!=p) {
      dfs(v,u);
      ve.insert(a[v]);
      res[u]+=res[v];
    }
  }
  int d=0;
  for (int el : ve) {
    if (el+a[u]<=k) {
      a[u]+=el;
    }
    else {
      d++;
    }
  }
  res[u]+=d;
}

void levi() {
  cin>>n>>k;
  for (int i=1;i<=n;++i) cin>>a[i];
  for (int i=1;i<=n-1;++i) {
    int u,v;
    cin>>u>>v;
    g[u].pb(v);
    g[v].pb(u);
  }
  dfs(1,0);
  cout<<res[1];
}

int32_t main() {
  // freopen("bbreeds.in","r",stdin);
  // freopen("bbreeds.out","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int tt=1;
  #ifdef tests
  cin>>tt;
  #endif
  while(tt--) levi();
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49