データ構造/素集合データ構造/部分永続 union-find
(test/data_structure/union-find/partially_persistent_union-find.test.cpp)

• View this file on GitHub
• Last update: 2023-07-21 12:14:05+09:00
• Problem: https://atcoder.jp/contests/agc002/tasks/agc002_d

Depends on

• 部分永続 union-find (include/emthrm/data_structure/union-find/partially_persistent_union-find.hpp)

Code

/*
 * @title データ構造/素集合データ構造/部分永続 union-find
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/agc002/tasks/agc002_d
 */

#include <iostream>
#include <numeric>

#include "emthrm/data_structure/union-find/partially_persistent_union-find.hpp"

int main() {
  int n, m;
  std::cin >> n >> m;
  emthrm::PartiallyPersistentUnionFind union_find(n);
  for (int i = 1; i <= m; ++i) {
    int a, b;
    std::cin >> a >> b;
    --a; --b;
    union_find.unite(i, a, b);
  }
  int q;
  std::cin >> q;
  while (q--) {
    int x, y, z;
    std::cin >> x >> y >> z;
    --x; --y;
    int lb = 0, ub = m;
    while (ub - lb > 1) {
      const int mid = std::midpoint(lb, ub);
      (union_find.size(mid, x) + (union_find.is_same(mid, x, y) ?
       0 : union_find.size(mid, y)) >= z ? ub : lb) = mid;
    }
    std::cout << lb + 1 << '\n';
  }
  return 0;
}

#line 1 "test/data_structure/union-find/partially_persistent_union-find.test.cpp"
/*
 * @title データ構造/素集合データ構造/部分永続 union-find
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/agc002/tasks/agc002_d
 */

#include <iostream>
#include <numeric>

#line 1 "include/emthrm/data_structure/union-find/partially_persistent_union-find.hpp"



#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>

namespace emthrm {

struct PartiallyPersistentUnionFind {
  explicit PartiallyPersistentUnionFind(const int n)
      : data(n, -1), last(n, -1), history(n, {{-1, -1}}) {}

  int root(const int t, const int ver) const {
    return last[ver] == -1 || t < last[ver] ? ver : root(t, data[ver]);
  }

  bool unite(const int t, int u, int v) {
    u = root(t, u);
    v = root(t, v);
    if (u == v) return false;
    if (data[u] > data[v]) std::swap(u, v);
    data[u] += data[v];
    data[v] = u;
    last[v] = t;
    history[u].emplace_back(t, data[u]);
    return true;
  }

  bool is_same(const int t, const int u, const int v) const {
    return root(t, u) == root(t, v);
  }

  int size(const int t, int ver) const {
    ver = root(t, ver);
    return -std::prev(std::lower_bound(history[ver].begin(),
                                       history[ver].end(),
                                       std::make_pair(t, 0)))->second;
  }

 private:
  std::vector<int> data, last;
  std::vector<std::vector<std::pair<int, int>>> history;
};

}  // namespace emthrm


#line 12 "test/data_structure/union-find/partially_persistent_union-find.test.cpp"

int main() {
  int n, m;
  std::cin >> n >> m;
  emthrm::PartiallyPersistentUnionFind union_find(n);
  for (int i = 1; i <= m; ++i) {
    int a, b;
    std::cin >> a >> b;
    --a; --b;
    union_find.unite(i, a, b);
  }
  int q;
  std::cin >> q;
  while (q--) {
    int x, y, z;
    std::cin >> x >> y >> z;
    --x; --y;
    int lb = 0, ub = m;
    while (ub - lb > 1) {
      const int mid = std::midpoint(lb, ub);
      (union_find.size(mid, x) + (union_find.is_same(mid, x, y) ?
       0 : union_find.size(mid, y)) >= z ? ub : lb) = mid;
    }
    std::cout << lb + 1 << '\n';
  }
  return 0;
}

Back to top page