C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
#include "emthrm/graph/reachability_on_dag.hpp"
ワードサイズを $W$ とおくと $O\left(\frac{Q(\lvert V \rvert + \lvert E \rvert)}{W} \right)$
template <typename CostType>
std::vector<bool> reachability_on_dag(const std::vector<std::vector<Edge<CostType>>>& graph, const std::vector<int>& ss, const std::vector<int>& ts);
https://atcoder.jp/contests/typical90/submissions/25153847
#ifndef EMTHRM_GRAPH_REACHABILITY_ON_DAG_HPP_ #define EMTHRM_GRAPH_REACHABILITY_ON_DAG_HPP_ #include <algorithm> #include <cassert> #include <cstdint> #include <limits> #include <utility> #include <vector> #include "emthrm/graph/edge.hpp" #include "emthrm/graph/topological_sort.hpp" namespace emthrm { template <typename CostType> std::vector<bool> reachability_on_dag( const std::vector<std::vector<Edge<CostType>>>& graph, const std::vector<int>& ss, const std::vector<int>& ts) { const int n = graph.size(), q = ss.size(); assert(std::cmp_equal(ts.size(), q)); const std::vector<int> order = topological_sort(graph); std::vector<bool> can_reach(q, false); std::vector<std::uint64_t> dp(n, 0); for (int i = 0; i < q;) { const int j = std::min(i + std::numeric_limits<std::uint64_t>::digits, q); std::fill(dp.begin(), dp.end(), 0); for (int k = i; k < j; ++k) { dp[ss[k]] |= UINT64_C(1) << (k - i); } for (const int node : order) { for (const int e : graph[node] | std::views::transform(&Edge<CostType>::dst)) { dp[e] |= dp[node]; } } for (int k = i; k < j; ++k) { can_reach[k] = dp[ts[k]] >> (k - i) & 1; } i = j; } return can_reach; } } // namespace emthrm #endif // EMTHRM_GRAPH_REACHABILITY_ON_DAG_HPP_
#line 1 "include/emthrm/graph/reachability_on_dag.hpp" #include <algorithm> #include <cassert> #include <cstdint> #include <limits> #include <utility> #include <vector> #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 1 "include/emthrm/graph/topological_sort.hpp" #include <queue> #include <ranges> #line 8 "include/emthrm/graph/topological_sort.hpp" #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 10 "include/emthrm/graph/topological_sort.hpp" namespace emthrm { template <typename CostType> std::vector<int> topological_sort( const std::vector<std::vector<Edge<CostType>>>& graph) { const int n = graph.size(); std::vector<int> deg(n, 0); for (const int e : graph | std::views::join | std::views::transform(&Edge<CostType>::dst)) { ++deg[e]; } std::queue<int> que; for (int i = 0; i < n; ++i) { if (deg[i] == 0) que.emplace(i); } std::vector<int> res; res.reserve(n); while (!que.empty()) { const int ver = que.front(); que.pop(); res.emplace_back(ver); for (const int e : graph[ver] | std::views::transform(&Edge<CostType>::dst)) { if (--deg[e] == 0) que.emplace(e); } } return std::cmp_equal(res.size(), n) ? res : std::vector<int>{}; } } // namespace emthrm #line 13 "include/emthrm/graph/reachability_on_dag.hpp" namespace emthrm { template <typename CostType> std::vector<bool> reachability_on_dag( const std::vector<std::vector<Edge<CostType>>>& graph, const std::vector<int>& ss, const std::vector<int>& ts) { const int n = graph.size(), q = ss.size(); assert(std::cmp_equal(ts.size(), q)); const std::vector<int> order = topological_sort(graph); std::vector<bool> can_reach(q, false); std::vector<std::uint64_t> dp(n, 0); for (int i = 0; i < q;) { const int j = std::min(i + std::numeric_limits<std::uint64_t>::digits, q); std::fill(dp.begin(), dp.end(), 0); for (int k = i; k < j; ++k) { dp[ss[k]] |= UINT64_C(1) << (k - i); } for (const int node : order) { for (const int e : graph[node] | std::views::transform(&Edge<CostType>::dst)) { dp[e] |= dp[node]; } } for (int k = i; k < j; ++k) { can_reach[k] = dp[ts[k]] >> (k - i) & 1; } i = j; } return can_reach; } } // namespace emthrm