comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: test/aoj/grl_5_c/grl_5_c.test.cpp

Depends on

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_C

#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/graph/class/edge/edge.hpp"
#include "src/graph/class/static-graph.hpp"
#include "src/graph/tree/offline-query/offline-query-lowest-common-ancestor.hpp"

#include <iostream>

namespace luz {

  void main_() {
    using edge  = Edge< i32 >;
    using graph = StaticGraph< edge >;

    usize n;
    std::cin >> n;

    graph g(n);
    for (usize v: rep(0, n)) {
      usize k;
      std::cin >> k;

      for ([[maybe_unused]] usize _: rep(0, k)) {
        usize u;
        std::cin >> u;
        g.add_undirected_edge(u, v);
      }
    }

    g.initialize();

    OfflineLCAQuery offline_lcas(g);

    usize q;
    std::cin >> q;

    std::vector< std::pair< usize, usize > > qs(q);
    for (auto &[u, v]: qs) {
      std::cin >> u >> v;
      offline_lcas.add_query(u, v);
    }

    offline_lcas.build(0);
    for (const auto &[u, v]: qs) {
      std::cout << offline_lcas.lca(u, v) << std::endl;
    }
  }

} // namespace luz

int main() {
  luz::main_();
}
#line 1 "test/aoj/grl_5_c/grl_5_c.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_C

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 2 "src/graph/class/edge/edge.hpp"

#line 4 "src/graph/class/edge/edge.hpp"

#include <vector>

namespace luz {

  template < typename T >
  class Edge {
   public:
    using cost_type = T;

    usize from, to;
    T cost;
    usize id;
    Edge() = default;
    Edge(usize from_, usize to_, T cost_, usize id_)
        : from(from_),
          to(to_),
          cost(cost_),
          id(id_) {}
  };

  template < typename T >
  using Edges = std::vector< Edge< T > >;

} // namespace luz
#line 2 "src/graph/class/static-graph.hpp"

#line 5 "src/graph/class/static-graph.hpp"

#line 7 "src/graph/class/static-graph.hpp"
#include <cassert>
#line 9 "src/graph/class/static-graph.hpp"

namespace luz::internal {

  template < typename Iterator >
  class OutgoingEdges {
    Iterator f, l;

   public:
    OutgoingEdges(Iterator f, Iterator l): f(f), l(l) {}

    Iterator begin() const {
      return f;
    }
    Iterator end() const {
      return l;
    }
    usize size() const {
      return l - f;
    }

    auto &operator[](usize k) {
      assert(k < size());
      return begin()[k];
    }
    const auto &operator[](usize k) const {
      assert(k < size());
      return begin()[k];
    }
  };

} // namespace luz::internal

namespace luz {

  template < typename Edge >
  class StaticGraph {

    using Edges          = std::vector< Edge >;
    using iterator       = typename Edges::iterator;
    using const_iterator = typename Edges::const_iterator;

    template < typename Iterator >
    using Es = internal::OutgoingEdges< Iterator >;

   protected:
    bool initialized;
    usize vertex_count;
    usize edge_count;

    Edges edges;
    std::vector< usize > outdegrees;

   public:
    using cost_type = typename Edge::cost_type;

    StaticGraph() = default;
    explicit StaticGraph(usize n)
        : initialized(false),
          vertex_count(n),
          edge_count(0),
          outdegrees(vertex_count) {}

    usize size() const {
      return vertex_count;
    }

    void initialize() {
      assert(not initialized);

      outdegrees.emplace_back(0);
      for (usize i: rrep(0, size())) {
        outdegrees[i] += outdegrees[i + 1];
      }

      std::sort(edges.begin(), edges.end(),
                [](const Edge &e1, const Edge &e2) {
        return e1.from != e2.from ? e1.from > e2.from : e1.to < e2.to;
      });

      initialized = true;
    }

    void add_directed_edge(usize from, usize to, cost_type cost = 1) {
      assert(not initialized);
      assert(from < size());
      assert(to < size());
      edges.emplace_back(from, to, cost, edge_count++);
      outdegrees[from]++;
    }

    void add_undirected_edge(usize u, usize v, cost_type cost = 1) {
      assert(not initialized);
      assert(u < size());
      assert(v < size());
      assert(u != v);
      edges.emplace_back(u, v, cost, edge_count);
      outdegrees[u]++;
      edges.emplace_back(v, u, cost, edge_count++);
      outdegrees[v]++;
    }

    Es< iterator > operator[](const usize &v) {
      assert(initialized);
      return Es< iterator >(edges.begin() + outdegrees[v + 1],
                            edges.begin() + outdegrees[v]);
    }

    const Es< const_iterator > operator[](const usize &v) const {
      assert(initialized);
      return Es< const_iterator >(edges.cbegin() + outdegrees[v + 1],
                                  edges.cbegin() + outdegrees[v]);
    }
  };

} // namespace luz
#line 2 "src/graph/tree/offline-query/offline-query-lowest-common-ancestor.hpp"

#line 2 "src/data-structure/disjoint-set-union.hpp"

#line 5 "src/data-structure/disjoint-set-union.hpp"

#line 9 "src/data-structure/disjoint-set-union.hpp"

namespace luz {

  class DisjointSetUnion {
    usize n;

    // vals[v] :=
    //   if v is root node: -1 * component size
    //   otherwise: parent node
    std::vector< isize > vals;

    void bound_check(usize v) const {
      assert(v < n);
    }

    usize impl_leader(usize v) {
      if (vals[v] < 0) return v;
      return vals[v] = leader(vals[v]);
    }

   public:
    DisjointSetUnion() = default;
    explicit DisjointSetUnion(usize n): n(n), vals(n, -1) {}

    usize size() const {
      return n;
    }

    usize leader(usize v) {
      bound_check(v);
      return impl_leader(v);
    }

    bool same(usize u, usize v) {
      bound_check(u), bound_check(v);
      return impl_leader(u) == impl_leader(v);
    }

    usize merge(usize u, usize v) {
      bound_check(u);
      bound_check(v);

      isize x = impl_leader(u);
      isize y = impl_leader(v);
      if (x == y) return x;
      if (-vals[x] < -vals[y]) std::swap(x, y);
      vals[x] += vals[y];
      vals[y] = x;
      return x;
    }

    usize group_size(usize v) {
      bound_check(v);
      return -vals[impl_leader(v)];
    }

    std::vector< std::vector< usize > > groups() {
      std::vector< std::vector< usize > > result(n);

      std::vector< usize > leaders(n), g_sizes(n);
      for (usize v: rep(0, n)) {
        leaders[v] = impl_leader(v);
        g_sizes[leaders[v]]++;
      }
      for (usize v: rep(0, n)) {
        result[v].reserve(g_sizes[v]);
      }
      for (usize v: rep(0, n)) {
        result[leaders[v]].emplace_back(v);
      }

      auto empty_check = [](const std::vector< usize > &vs) {
        return vs.empty();
      };
      result.erase(
          std::remove_if(result.begin(), result.end(), empty_check),
          result.end());

      return result;
    }
  };

} // namespace luz
#line 2 "src/utility/pair-hash.hpp"

#line 4 "src/utility/pair-hash.hpp"

#include <functional>
#include <utility>

namespace luz {

  class PairHash {
    template < typename T >
    usize hash_combine(usize hr, const T &x) const {
      usize h = std::hash< T >()(x);
      return hr ^ (h + (hr << 11) + (hr >> 13));
    }

   public:
    template < typename F, typename S >
    usize operator()(const std::pair< F, S > &p) const {
      return hash_combine(hash_combine(0, p.first), p.second);
    }
  };

} // namespace luz
#line 7 "src/graph/tree/offline-query/offline-query-lowest-common-ancestor.hpp"

#line 9 "src/graph/tree/offline-query/offline-query-lowest-common-ancestor.hpp"
#include <unordered_map>
#line 12 "src/graph/tree/offline-query/offline-query-lowest-common-ancestor.hpp"

namespace luz {

  template < class G >
  class OfflineLCAQuery {
    using graph     = G;
    using cost_type = typename G::cost_type;
    usize g_size;
    graph g;

    usize query_count;
    std::vector< std::vector< usize > > qs;

    DisjointSetUnion dsu;
    std::vector< bool > visited;
    std::vector< usize > ancestors;

    using query_type = std::pair< usize, usize >;
    std::unordered_map< query_type, usize, PairHash > results;

    void bound_check(usize v) const {
      assert(v < g_size);
    }

    void dfs(usize v) {
      visited[v]   = true;
      ancestors[v] = v;

      for (const auto &e: g[v]) {
        if (visited[e.to]) continue;
        dfs(e.to);
        dsu.merge(v, e.to);
        ancestors[dsu.leader(v)] = v;
      }

      for (const auto &u: qs[v]) {
        if (not visited[u]) continue;
        results[query_type(u, v)] = results[query_type(v, u)] =
            ancestors[dsu.leader(u)];
      }
    }

   public:
    using Queries = std::vector< std::pair< usize, usize > >;

    OfflineLCAQuery(G &g)
        : g_size(g.size()),
          g(g),
          query_count(0),
          qs(g_size),
          dsu(g_size),
          visited(g_size, false),
          ancestors(g_size) {}

    void add_query(usize u, usize v) {
      bound_check(u);
      bound_check(v);
      qs[u].emplace_back(v);
      qs[v].emplace_back(u);
      query_count++;
    }

    void build(usize root) {
      bound_check(root);
      results.reserve(2 * query_count);
      dfs(root);
    }

    usize lca(usize u, usize v) {
      bound_check(u);
      bound_check(v);
      query_type qi(u, v);
      assert(results.count(qi));
      return results[qi];
    }
  };

} // namespace luz
#line 9 "test/aoj/grl_5_c/grl_5_c.test.cpp"

#include <iostream>

namespace luz {

  void main_() {
    using edge  = Edge< i32 >;
    using graph = StaticGraph< edge >;

    usize n;
    std::cin >> n;

    graph g(n);
    for (usize v: rep(0, n)) {
      usize k;
      std::cin >> k;

      for ([[maybe_unused]] usize _: rep(0, k)) {
        usize u;
        std::cin >> u;
        g.add_undirected_edge(u, v);
      }
    }

    g.initialize();

    OfflineLCAQuery offline_lcas(g);

    usize q;
    std::cin >> q;

    std::vector< std::pair< usize, usize > > qs(q);
    for (auto &[u, v]: qs) {
      std::cin >> u >> v;
      offline_lcas.add_query(u, v);
    }

    offline_lcas.build(0);
    for (const auto &[u, v]: qs) {
      std::cout << offline_lcas.lca(u, v) << std::endl;
    }
  }

} // namespace luz

int main() {
  luz::main_();
}
Back to top page