Submission #1187385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187385		mannshah1211	Mergers (JOI19_mergers)	C++20	0 / 100	29 ms	20152 KiB

mergers

/**
 *   author: tourist
 *   created: 17.04.2025 15:40:37
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  int get(int x) {
    if (p[x] == x) {
      return x;
    }
    return p[x] = get(p[x]);
  }

  bool unite(int u, int v) {
    u = get(u);
    v = get(v);
    if (u != v) {
      p[v] = u;
      return true;
    }
    return false;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> s(n);
  vector<vector<int>> at(k);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    --s[i];
    at[s[i]].push_back(i);
  }
  vector<int> tin(n), tout(n);
  vector<vector<int>> pv(n, vector<int>(19));
  int timer = 0;
  auto Dfs = [&](auto&& self, int v, int pr) -> void {
    tin[v] = timer++;
    pv[v][0] = pr;
    for (int u : g[v]) {
      if (u != pr) {
        self(self, u, v);
      }
    }
    tout[v] = timer;
  };
  Dfs(Dfs, 0, -1);
  auto Anc = [&](int u, int v) {
    return (tin[u] <= tin[v]) && (tout[u] <= tout[v]);
  };
  auto lca = [&](int u, int v) {
    if (Anc(u, v)) {
      return u;
    }
    for (int b = 18; b >= 0; b--) {
      if (pv[u][b] != -1 && !Anc(pv[u][b], v)) {
        u = pv[u][b];
      }
    }
    assert(pv[u][0] != -1);
    return pv[u][0];
  };
  vector<int> values(n);
  auto Add = [&](int u, int v) {
    if (Anc(u, v)) {
      values[u] += 1;
      values[v] -= 1;
      return;
    }
    if (Anc(v, u)) {
      values[v] += 1;
      values[u] -= 1;
      return;
    }
    int w = lca(u, v);
    values[w] += 1;
    values[u] -= 1;
    values[v] -= 1;
  };
  for (int i = 0; i < k; i++) {
    sort(at[i].begin(), at[i].end(), [&](int u, int v) {
      return (tin[u] < tin[v]);
    });
    for (int j = 0; j < static_cast<int>(at[i].size()) - 1; j++) {
      Add(at[i][j], at[i][j + 1]);
    }
  }
  int sum = 0;
  auto Accumulate = [&](auto&& self, int v, int pr) -> void {
    int original = values[v];
    values[v] = sum;
    sum += original;
    for (int u : g[v]) {
      if (u != pr) {
        self(self, u, v);
      }
    }
    sum -= original;
  };  
  Accumulate(Accumulate, 0, -1);
  dsu ds(n);
  for (int v = 1; v < n; v++) {
    if (values[v] != 0) {
      ds.unite(v, pv[v][0]);
    }
  }
  vector<int> component_values;
  for (int v = 0; v < n; v++) {
    component_values.push_back(ds.get(v));
  }
  vector<int> who(n, -1);
  int ptr = 0;
  for (int i = 0; i < n; i++) {
    if (who[component_values[i]] == -1) {
      who[component_values[i]] = ptr;
      ptr++;
    }
  }
  vector<int> deg(ptr);
  for (int v = 1; v < n; v++) {
    if (values[v] == 0) {
      ++deg[who[ds.get(pv[v][0])]];
      ++deg[who[ds.get(v)]];
    }
  }
  int leaves = 0;
  for (int i = 0; i < ptr; i++) {
    if (deg[i] == 1) {
      leaves++;
    }
  }
  cout << (leaves + 1) / 2 << '\n';
  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30