proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/partially_persistent_dsu/same_and_size.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE
// Source: https://atcoder.jp/contests/agc002/tasks/agc002_d

#include <iostream>
#include "tools/assert_that.hpp"
#include "tools/partially_persistent_dsu.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  const int N = 5;
  const int M = 6;
  tools::partially_persistent_dsu dsu(N);
  dsu.merge(1, 2);
  dsu.merge(3, 4);
  dsu.merge(0, 1);
  dsu.merge(0, 2);
  dsu.merge(0, 3);
  dsu.merge(0, 4);

  const auto query = [&](const int x, const int y, const int z) {
    int ng = 0;
    int ok = M;
    while (ok - ng > 1) {
      const auto t = (ng + ok) / 2;
      if (z <= dsu.size(t, x) + (dsu.same(t, x, y) ? 0 : dsu.size(t, y))) {
        ok = t;
      } else {
        ng = t;
      }
    }
    return ok;
  };

  assert_that(query(1, 3, 3) == 1);
  assert_that(query(1, 3, 4) == 2);
  assert_that(query(1, 3, 5) == 3);
  assert_that(query(0, 2, 3) == 1);
  assert_that(query(0, 2, 4) == 5);
  assert_that(query(0, 2, 5) == 5);

  return 0;
}

#line 1 "tests/partially_persistent_dsu/same_and_size.test.cpp"
// competitive-verifier: STANDALONE
// Source: https://atcoder.jp/contests/agc002/tasks/agc002_d

#include <iostream>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/partially_persistent_dsu.hpp"



#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>
#include <optional>
#include <queue>
#include <utility>
#include <vector>
#line 1 "tools/less_by_first.hpp"



#line 5 "tools/less_by_first.hpp"

namespace tools {

  struct less_by_first {
    template <typename T1, typename T2>
    bool operator()(const std::pair<T1, T2>& x, const std::pair<T1, T2>& y) const {
      return x.first < y.first;
    }
  };
}


#line 13 "tools/partially_persistent_dsu.hpp"

namespace tools {
  class partially_persistent_dsu {
    int m_now;
    std::vector<std::pair<int, int>> m_parents;
    std::vector<std::vector<std::pair<int, int>>> m_sizes;
    std::vector<int> m_merge_times;

  public:
    partially_persistent_dsu() = default;
    explicit partially_persistent_dsu(const int n) :
      m_now(0),
      m_parents(n, std::make_pair(std::numeric_limits<int>::max(), -1)),
      m_sizes(n, std::vector<std::pair<int, int>>{std::make_pair(0, 1)}) {
    }

    int now() const {
      return this->m_now;
    }

    int leader(const int t, const int x) const {
      assert(0 <= t && t <= this->m_now);
      assert(0 <= x && x < this->size());

      return t < this->m_parents[x].first ? x : this->leader(t, this->m_parents[x].second);
    }

    bool same(const int t, const int x, const int y) const {
      assert(0 <= t && t <= this->m_now);
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      return this->leader(t, x) == this->leader(t, y);
    }

    std::optional<std::pair<int, int>> merge(int x, int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      ++this->m_now;

      x = this->leader(this->m_now, x);
      y = this->leader(this->m_now, y);
      if (x == y) return std::nullopt;

      if (this->m_sizes[x].back().second < this->m_sizes[y].back().second) std::swap(x, y);

      this->m_parents[y] = std::make_pair(this->m_now, x);
      this->m_sizes[x].emplace_back(this->m_now, this->m_sizes[x].back().second + this->m_sizes[y].back().second);

      this->m_merge_times.push_back(this->m_now);

      return std::make_pair(x, y);
    }

    int size() const {
      return this->m_parents.size();
    }

    int size(const int t, int x) const {
      assert(0 <= t && t <= this->m_now);
      assert(0 <= x && x < this->size());

      x = this->leader(t, x);
      auto it = std::upper_bound(this->m_sizes[x].begin(), this->m_sizes[x].end(), std::make_pair(t, 0), tools::less_by_first());
      --it;
      return it->second;
    }

    std::vector<std::vector<int>> groups(const int t) const {
      assert(0 <= t && t <= this->m_now);

      std::vector<std::vector<int>> graph(this->size());
      for (int i = 0; i < this->size(); ++i) {
        if (this->m_parents[i].first <= t) graph[this->m_parents[i].second].push_back(i);
      }

      std::vector<std::vector<int>> res(this->size());
      for (int root = 0; root < this->size(); ++root) {
        if (t < this->m_parents[root].first) {
          std::queue<int> queue({root});
          while (!queue.empty()) {
            const auto here = queue.front();
            queue.pop();
            res[root].push_back(here);
            for (const auto next : graph[here]) {
              queue.push(next);
            }
          }
        }
      }

      res.erase(std::remove_if(res.begin(), res.end(), [](const auto& group) { return group.empty(); }), res.end());
      return res;
    }

    int ncc(const int t) const {
      assert(0 <= t && t <= this->m_now);
      return this->size() - std::distance(this->m_merge_times.begin(), std::ranges::upper_bound(this->m_merge_times, t));
    }

    int when_connected(const int x, const int y) const {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      std::vector<int> x_ancestors;
      for (int v = x; v != -1; v = this->m_parents[v].second) {
        x_ancestors.push_back(v);
      }
      const int xl = x_ancestors.size();

      std::vector<int> y_ancestors;
      for (int v = y; v != -1; v = this->m_parents[v].second) {
        y_ancestors.push_back(v);
      }
      const int yl = y_ancestors.size();

      int d = 0;
      for (; xl - d - 1 >= 0 && yl - d - 1 >= 0 && x_ancestors[xl - d - 1] == y_ancestors[yl - d - 1]; ++d);

      return d == 0 ? std::numeric_limits<int>::max() : std::max(
        xl - d - 1 >= 0 ? this->m_parents[x_ancestors[xl - d - 1]].first : 0,
        yl - d - 1 >= 0 ? this->m_parents[y_ancestors[yl - d - 1]].first : 0
      );
    }
  };
}


#line 7 "tests/partially_persistent_dsu/same_and_size.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  const int N = 5;
  const int M = 6;
  tools::partially_persistent_dsu dsu(N);
  dsu.merge(1, 2);
  dsu.merge(3, 4);
  dsu.merge(0, 1);
  dsu.merge(0, 2);
  dsu.merge(0, 3);
  dsu.merge(0, 4);

  const auto query = [&](const int x, const int y, const int z) {
    int ng = 0;
    int ok = M;
    while (ok - ng > 1) {
      const auto t = (ng + ok) / 2;
      if (z <= dsu.size(t, x) + (dsu.same(t, x, y) ? 0 : dsu.size(t, y))) {
        ok = t;
      } else {
        ng = t;
      }
    }
    return ok;
  };

  assert_that(query(1, 3, 3) == 1);
  assert_that(query(1, 3, 4) == 2);
  assert_that(query(1, 3, 5) == 3);
  assert_that(query(0, 2, 3) == 1);
  assert_that(query(0, 2, 4) == 5);
  assert_that(query(0, 2, 5) == 5);

  return 0;
}
Back to top page