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/ITP1_1_A #include "src/graph/functional-graph/online-query/online-query-jump-on-functional-graph.hpp" #include "src/cpp-template/header/int-alias.hpp" #include "src/cpp-template/header/size-alias.hpp" #include "src/graph/class/edge/edge.hpp" #include "src/graph/class/static-graph.hpp" #include <cassert> #include <iostream> #include <vector> namespace luz { template < class G > usize naive(const G &fg, usize v, u64 k) { if (k == 0) { return v; } else { return naive(fg, fg[v][0].to, k - 1); } } void main_() { using edge = Edge< u32 >; using graph = StaticGraph< edge >; graph fg(10); fg.add_directed_edge(0, 1); fg.add_directed_edge(1, 3); fg.add_directed_edge(2, 2); fg.add_directed_edge(3, 0); fg.add_directed_edge(4, 5); fg.add_directed_edge(5, 7); fg.add_directed_edge(6, 8); fg.add_directed_edge(7, 8); fg.add_directed_edge(8, 9); fg.add_directed_edge(9, 7); fg.initialize(); OnlineJumpOnFunctionalGraphQuery online_jump_on_functional_graph_solver(fg); const u64 large = 1000000000000000000ll; std::vector< usize > expected{1, 3, 2, 0, 9, 7, 8, 8, 9, 7}; for (usize v: rep(0, 10)) { for (u64 k: rep(0, 100)) { assert(online_jump_on_functional_graph_solver.jump(v, k) == naive(fg, v, k)); } assert(online_jump_on_functional_graph_solver.jump(v, large) == expected[v]); } std::cout << "Hello World" << std::endl; } } // namespace luz int main() { luz::main_(); }
#line 1 "unit-test/graph/online-query-jump-on-functional-graph.test.cpp" // verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ITP1_1_A #line 2 "src/graph/functional-graph/online-query/online-query-jump-on-functional-graph.hpp" #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/utility/bit/bit-width.hpp" #line 2 "src/utility/bit/popcount.hpp" #line 5 "src/utility/bit/popcount.hpp" #include <cassert> namespace luz { usize popcount(u64 x) { assert(__cplusplus <= 201703L); #ifdef __GNUC__ return __builtin_popcountll(x); #endif x -= (x >> 1) & 0x5555555555555555; x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); x += (x >> 4) & 0x0f0f0f0f0f0f0f0f; return x * 0x0101010101010101 >> 56 & 0x7f; } } // namespace luz #line 6 "src/utility/bit/bit-width.hpp" #line 8 "src/utility/bit/bit-width.hpp" namespace luz { usize bit_width(u64 x) { assert(__cplusplus <= 201703L); if (x == 0) { return 0; } #ifdef __GNUC__ return 64 - __builtin_clzll(x); #endif x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x |= x >> 32; return popcount(x); } } // namespace luz #line 7 "src/graph/functional-graph/online-query/online-query-jump-on-functional-graph.hpp" #line 9 "src/graph/functional-graph/online-query/online-query-jump-on-functional-graph.hpp" #include <utility> #include <vector> namespace luz { template < class G > class OnlineJumpOnFunctionalGraphQuery { using graph = G; using cost_type = typename graph::cost_type; usize g_size; graph g; usize LOG; std::vector< std::vector< usize > > doubling_table; std::vector< usize > loop_id, loop_size, loop_pos; std::vector< std::vector< usize > > loops; void check_functional_graph() const { for (usize v: rep(0, g_size)) { assert(g[v].size() == 1); } } void build_doubling_table() { for (usize k: rep(0, LOG)) { for (usize v: rep(0, g_size)) { doubling_table[k][v] = (k ? doubling_table[k - 1][doubling_table[k - 1][v]] : g[v][0].to); } } } std::vector< usize > get_indegrees() const { std::vector< usize > indegrees(g_size); for (usize v: rep(0, g_size)) { indegrees[g[v][0].to]++; } return indegrees; } void delete_leaves(std::vector< usize > &indegrees) { std::vector< usize > leaves; leaves.reserve(g_size); for (usize v: rep(0, g_size)) { if (indegrees[v] > 0) { continue; } leaves.emplace_back(v); } while (not leaves.empty()) { usize v = leaves.back(); leaves.pop_back(); usize u = g[v][0].to; indegrees[u]--; if (indegrees[u] == 0) { leaves.emplace_back(u); } } } void construct_loops() { std::vector< usize > indegrees = get_indegrees(); delete_leaves(indegrees); for (usize v: rep(0, g_size)) { if (indegrees[v] == 0) { continue; } usize cur = v; std::vector< usize > loop; do { loop_id[cur] = loops.size(); loop_pos[cur] = loop.size(); loop.emplace_back(cur); indegrees[cur] = 0; cur = g[cur][0].to; } while (cur != v); do { loop_size[cur] = loop.size(); cur = g[cur][0].to; } while (cur != v); loops.emplace_back(std::move(loop)); } } usize jump_small(usize v, usize k) const { assert(k < g_size); for (usize i: rep(0, LOG)) { if ((k & 1) == 1) { v = doubling_table[i][v]; } k >>= 1; } return v; } public: OnlineJumpOnFunctionalGraphQuery(const graph &g_) : g_size(g_.size()), g(g_), LOG(bit_width(g_size - 1)), doubling_table(LOG, std::vector< usize >(g_size)), loop_id(g_size, -1), loop_size(g_size), loop_pos(g_size, -1) { check_functional_graph(); assert(g_size != 0); build_doubling_table(); construct_loops(); } usize jump(usize v, u64 k) const { assert(v < g_size); if (k == 0) { return v; } if (k < g_size) { return jump_small(v, k); } v = jump_small(v, g_size - 1); k -= (g_size - 1); const auto &loop = loops[loop_id[v]]; k += loop_pos[v]; k %= loop_size[v]; return loop[k]; } }; } // namespace luz #line 4 "unit-test/graph/online-query-jump-on-functional-graph.test.cpp" #line 2 "src/graph/class/edge/edge.hpp" #line 4 "src/graph/class/edge/edge.hpp" #line 6 "src/graph/class/edge/edge.hpp" 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 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 9 "unit-test/graph/online-query-jump-on-functional-graph.test.cpp" #line 11 "unit-test/graph/online-query-jump-on-functional-graph.test.cpp" #include <iostream> #line 13 "unit-test/graph/online-query-jump-on-functional-graph.test.cpp" namespace luz { template < class G > usize naive(const G &fg, usize v, u64 k) { if (k == 0) { return v; } else { return naive(fg, fg[v][0].to, k - 1); } } void main_() { using edge = Edge< u32 >; using graph = StaticGraph< edge >; graph fg(10); fg.add_directed_edge(0, 1); fg.add_directed_edge(1, 3); fg.add_directed_edge(2, 2); fg.add_directed_edge(3, 0); fg.add_directed_edge(4, 5); fg.add_directed_edge(5, 7); fg.add_directed_edge(6, 8); fg.add_directed_edge(7, 8); fg.add_directed_edge(8, 9); fg.add_directed_edge(9, 7); fg.initialize(); OnlineJumpOnFunctionalGraphQuery online_jump_on_functional_graph_solver(fg); const u64 large = 1000000000000000000ll; std::vector< usize > expected{1, 3, 2, 0, 9, 7, 8, 8, 9, 7}; for (usize v: rep(0, 10)) { for (u64 k: rep(0, 100)) { assert(online_jump_on_functional_graph_solver.jump(v, k) == naive(fg, v, k)); } assert(online_jump_on_functional_graph_solver.jump(v, large) == expected[v]); } std::cout << "Hello World" << std::endl; } } // namespace luz int main() { luz::main_(); }