Submission #1231591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231591		lopkus	Paprike (COI18_paprike)	C++20	100 / 100	82 ms	21424 KiB

paprike

#include <bits/stdc++.h>

#define int int64_t

const int N = 1e5 + 5;

std::vector<int> a(N);

signed main() {
  int n, k;
  std::cin >> n >> k;
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<int> adj[n + 1];
  for(int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  int ans = 0;
  std::vector<int> s(n + 1);
  std::function<void(int, int)> dfs = [&] (int v, int p) {
    for(auto u : adj[v]) {
      if(u == p) {
        continue;
      }
      dfs(u, v);
    }
    std::vector<int> t;
    for(auto u : adj[v]) {
      if(u == p) {
        continue;
      }
      t.push_back(s[u]);
    }
    std::sort(t.begin(), t.end());
    s[v] = a[v];
    for(int i = 0; i < t.size(); i++) {
      if(s[v] + t[i] <= k) {
        s[v] += t[i];
      }
      else {
        ans += 1;
      }
    }
  };
  dfs(1, 0);
  std::cout << ans;
}

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