Submission #1231590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231590		lopkus	Paprike (COI18_paprike)	C++20	0 / 100	90 ms	40520 KiB

paprike

#include <bits/stdc++.h>

#define int int64_t

const int N = 1e5 + 5;

std::vector<int> p(N);
std::vector<int> Dsu[N];
std::vector<int> sum(N);
std::vector<int> a(N);

struct dsu {
  void add(int i) {
    p[i] = i;
    Dsu[i].push_back(i);
    sum[i] = a[i];
  }
  int parent(int u) {
    return p[u];
  }
  int Get(int u) {
    return sum[p[u]];
  }
  void connect(int u, int v) {
    u = p[u];
    v = p[v];
    if(u == v) {
      return;
    }
    if(Dsu[u].size() > Dsu[v].size()) {
      std::swap(u, v);
    }
    for(auto e : Dsu[u]) {
      Dsu[v].push_back(e);
      p[e] = v;
      sum[v] += a[e];
    }
    Dsu[u].clear();
  }
}dsu;

signed main() {
  int n, k;
  std::cin >> n >> k;
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  for(int i = 1; i <= n; i++) {
    dsu.add(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);
  }
  std::function<void(int, int)> dfs = [&] (int v, int p) {
    for(auto u : adj[v]) {
      if(u == p) {
        continue;
      }
      dfs(u, v);
    }
    if(adj[v].size() == 1) {
      // create

      return;
    }
    std::vector<std::array<int, 2>> t;
    for(auto u : adj[v]) {
      if(u == p) {
        continue;
      }
      t.push_back({dsu.Get(u), dsu.parent(u)});
    }
    std::sort(t.begin(), t.end());
    for(int i = 0; i < t.size(); i++) {
      if(dsu.Get(dsu.parent(v)) + t[i][0] <= k) {
        dsu.connect(dsu.parent(v), t[i][1]);
      }
    }
  };
  dfs(1, 0);
  std::set<int> st;
  for(int i = 1; i <= n; i++) {
    st.insert(dsu.parent(i));
  }
  std::cout << ((int)st.size()) - 1;
}

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