This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub luzhiled1333/comp-library
// 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_(); }