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/when_connected.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE
// Source: https://atcoder.jp/contests/abc394/tasks/abc394_g

#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/less_equal_zeta_inplace.hpp"
#include "tools/lower_bound.hpp"
#include "tools/partially_persistent_dsu.hpp"

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

  const int H = 3;
  const int W = 3;
  const std::vector<std::vector<int>> F = {
    {12, 10, 6},
    {1, 1, 3},
    {8, 6, 7},
  };

  const auto p = [&](const auto y, const auto x) {
    return y * W + x;
  };

  std::vector<std::vector<std::pair<int, int>>> edges(1000000);
  for (int y = 0; y < H; ++y) {
    for (int x = 0; x < W; ++x) {
      if (y - 1 >= 0) {
        edges[1000000 - std::min(F[y][x], F[y - 1][x])].emplace_back(p(y, x), p(y - 1, x));
      }
      if (x - 1 >= 0) {
        edges[1000000 - std::min(F[y][x], F[y][x - 1])].emplace_back(p(y, x), p(y, x - 1));
      }
    }
  }

  std::vector<int> tally(1000001, 0);
  for (int f = 0; f < 1000000; ++f) {
    tally[f + 1] = edges[f].size();
  }
  tools::less_equal_zeta_inplace(tally);

  tools::partially_persistent_dsu dsu(H * W);
  for (const auto& edges_at_f : edges) {
    for (const auto& [u, v] : edges_at_f) {
      dsu.merge(u, v);
    }
  }

  const auto query = [&](const int A, const int B, const int Y, const int C, const int D, const int Z) {
    const auto f = 1000001 - tools::lower_bound(tally, dsu.when_connected(p(A, B), p(C, D)));
    return Y <= f && Z <= f ? std::abs(Y - Z) : std::abs(Y - f) + std::abs(Z - f);
  };

  assert_that(query(0, 0, 10, 2, 0, 6) == 10);
  assert_that(query(0, 0, 6, 0, 1, 4) == 2);

  return 0;
}

#line 1 "tests/partially_persistent_dsu/when_connected.test.cpp"
// competitive-verifier: STANDALONE
// Source: https://atcoder.jp/contests/abc394/tasks/abc394_g

#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
#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/less_equal_zeta_inplace.hpp"



#include <iterator>
#include <ranges>
#line 1 "tools/groups.hpp"



#include <cstddef>
#include <type_traits>
#line 1 "tools/arithmetic.hpp"



#include <concepts>
#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 6 "tools/arithmetic.hpp"

namespace tools {
  template <typename T>
  concept arithmetic = tools::integral<T> || std::floating_point<T>;
}


#line 7 "tools/groups.hpp"

namespace tools {
  namespace groups {
    template <typename G>
    struct bit_xor {
      using T = G;
      static T op(const T& x, const T& y) {
        return x ^ y;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& x) {
        return x;
      }
    };

    template <typename G>
    struct multiplies {
      using T = G;
      static T op(const T& x, const T& y) {
        return x * y;
      }
      static T e() {
        return T(1);
      }
      static T inv(const T& x) {
        return e() / x;
      }
    };

    template <typename G>
    struct plus {
      using T = G;
      static T op(const T& x, const T& y) {
        return x + y;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& x) {
        return -x;
      }
    };
  }
}


#line 1 "tools/monoid.hpp"



#line 5 "tools/monoid.hpp"

namespace tools {
  template <typename M>
  concept monoid = requires(typename M::T x, typename M::T y) {
    { M::op(x, y) } -> std::same_as<typename M::T>;
    { M::e() } -> std::same_as<typename M::T>;
  };
}


#line 9 "tools/less_equal_zeta_inplace.hpp"

namespace tools {
  template <tools::monoid M, std::ranges::random_access_range R>
  requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
  void less_equal_zeta_inplace(R&& a) {
    const int N = std::ranges::distance(a);
    for (int i = 1; i < N; ++i) {
      std::ranges::begin(a)[i] = M::op(std::ranges::begin(a)[i - 1], std::ranges::begin(a)[i]);
    }
  }

  template <std::ranges::random_access_range R>
  requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
  void less_equal_zeta_inplace(R&& a) {
    tools::less_equal_zeta_inplace<tools::groups::plus<std::ranges::range_value_t<R>>>(std::forward<R>(a));
  }
}


#line 1 "tools/lower_bound.hpp"



#line 5 "tools/lower_bound.hpp"
#include <functional>
#line 8 "tools/lower_bound.hpp"

namespace tools {

  template <
    std::random_access_iterator I,
    std::sentinel_for<I> S,
    typename Proj = std::identity,
    typename T = std::remove_cvref_t<std::invoke_result_t<Proj&, std::iter_value_t<I>&>>,
    std::indirect_strict_weak_order<const T*, std::projected<I, Proj>> Comp = std::ranges::less
  >
  constexpr std::iter_difference_t<I> lower_bound(const I first, const S last, const T& value, const Comp comp = {}, const Proj proj = {}) {
    return std::ranges::distance(first, std::ranges::lower_bound(first, last, value, comp, proj));
  }

  template <
    std::ranges::random_access_range R,
    typename Proj = std::identity,
    typename T = std::remove_cvref_t<std::invoke_result_t<Proj&, std::ranges::range_value_t<R>&>>,
    std::indirect_strict_weak_order<const T*, std::projected<std::ranges::iterator_t<R>, Proj>> Comp = std::ranges::less
  >
  constexpr std::ranges::range_difference_t<R> lower_bound(R&& r, const T& value, const Comp comp = {}, const Proj proj = {}) {
    return std::ranges::distance(std::ranges::begin(r), std::ranges::lower_bound(r, value, comp, proj));
  }
}


#line 1 "tools/partially_persistent_dsu.hpp"



#line 5 "tools/partially_persistent_dsu.hpp"
#include <cassert>
#line 7 "tools/partially_persistent_dsu.hpp"
#include <limits>
#include <optional>
#include <queue>
#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 13 "tests/partially_persistent_dsu/when_connected.test.cpp"

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

  const int H = 3;
  const int W = 3;
  const std::vector<std::vector<int>> F = {
    {12, 10, 6},
    {1, 1, 3},
    {8, 6, 7},
  };

  const auto p = [&](const auto y, const auto x) {
    return y * W + x;
  };

  std::vector<std::vector<std::pair<int, int>>> edges(1000000);
  for (int y = 0; y < H; ++y) {
    for (int x = 0; x < W; ++x) {
      if (y - 1 >= 0) {
        edges[1000000 - std::min(F[y][x], F[y - 1][x])].emplace_back(p(y, x), p(y - 1, x));
      }
      if (x - 1 >= 0) {
        edges[1000000 - std::min(F[y][x], F[y][x - 1])].emplace_back(p(y, x), p(y, x - 1));
      }
    }
  }

  std::vector<int> tally(1000001, 0);
  for (int f = 0; f < 1000000; ++f) {
    tally[f + 1] = edges[f].size();
  }
  tools::less_equal_zeta_inplace(tally);

  tools::partially_persistent_dsu dsu(H * W);
  for (const auto& edges_at_f : edges) {
    for (const auto& [u, v] : edges_at_f) {
      dsu.merge(u, v);
    }
  }

  const auto query = [&](const int A, const int B, const int Y, const int C, const int D, const int Z) {
    const auto f = 1000001 - tools::lower_bound(tally, dsu.when_connected(p(A, B), p(C, D)));
    return Y <= f && Z <= f ? std::abs(Y - Z) : std::abs(Y - f) + std::abs(Z - f);
  };

  assert_that(query(0, 0, 10, 2, 0, 6) == 10);
  assert_that(query(0, 0, 6, 0, 1, 4) == 2);

  return 0;
}
Back to top page