Submission #1043894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043894		vjudge1	Paprike (COI18_paprike)	C++17	13 / 100	64 ms	15700 KiB

paprike

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100'000 + 10;
int n, k, par[N], c[N];
ll a[N];
vector<int> G[N];

void dfs(int v, int p = 0)
{
  par[v] = p;
  for(int u : G[v])
    if(u != p)
      dfs(u, v), c[v]++;
}

int main()
{
  cin >> n >> k;
  for(int i = 1; i <= n; i++)
    cin >> a[i];
  
  for(int i = 1; i < n; i ++)
    {
      int u, v;
      cin >> u >> v;
      G[u].push_back(v);
      G[v].push_back(u);
    }

  dfs(1);
  int ans = 0;
  set<pair<ll,int> > st;
  for(int i = 2; i <= n; i ++)
    if(c[i] == 0)
      st.insert({a[i], i});

  while(st.size())
    {
      int v = st.begin()->second;
      st.erase(st.begin());
      // cerr << v << ' ' << a[v] << ' ' << par[v] << ' ' << a[par[v]] << endl;
      if(a[par[v]] + a[v] <= k)
	a[par[v]] += a[v];
      else
	ans++;

      c[par[v]]--;
      if(c[par[v]] == 0 && par[v] != 1)
	st.insert({a[par[v]], par[v]});
      
    }
  
  cout << ans << endl;
  return 0;
}

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