This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/abc287/tasks/abc287_Ex" #include <iostream> #include "library/graph/minmax_floyd_warshall.hpp" constexpr int inf = std::numeric_limits<int>::max() / 2; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<std::vector<int>> g(n, std::vector<int>(n, inf)); for (int i = 0; i < m; ++i) { int u, v; std::cin >> u >> v; --u, --v; g[u][v] = std::max(u, v) + 1; } std::vector<std::vector<int>> ans = suisen::minmax_floyd_warshall(g); int q; std::cin >> q; for (int i = 0; i < q; ++i) { int s, t; std::cin >> s >> t; --s, --t; std::cout << (ans[s][t] == inf ? -1 : ans[s][t]) << '\n'; } }
#line 1 "test/src/graph/minmax_floyd_warshall/abc287_h.test.cpp" #define PROBLEM "https://atcoder.jp/contests/abc287/tasks/abc287_Ex" #include <iostream> #line 1 "library/graph/minmax_floyd_warshall.hpp" #include <algorithm> #include <cstdint> #include <functional> #include <tuple> #include <vector> #line 1 "library/util/subset_iterator.hpp" #ifdef _MSC_VER # include <intrin.h> #else # include <x86intrin.h> #endif #include <cassert> #line 13 "library/util/subset_iterator.hpp" #include <limits> namespace suisen { template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> struct all_subset { struct all_subset_iter { const T s; T t; constexpr all_subset_iter(T s) : s(s), t(s + 1) {} constexpr auto operator*() const { return t; } constexpr auto operator++() {} constexpr auto operator!=(std::nullptr_t) { return t ? (--t &= s, true) : false; } }; T s; constexpr all_subset(T s) : s(s) {} constexpr auto begin() { return all_subset_iter(s); } constexpr auto end() { return nullptr; } }; // iterator over T s.t. T is subset of S and |T| = k struct all_subset_k { struct all_subset_k_iter { const uint32_t n, k, s; uint32_t t; __attribute__((target("avx2"))) all_subset_k_iter(uint32_t s, uint32_t k) : n(uint32_t(1) << _mm_popcnt_u32(s)), k(k), s(s), t((uint32_t(1) << k) - 1) {} __attribute__((target("bmi2"))) auto operator*() const { return _pdep_u32(t, s); } __attribute__((target("bmi"))) auto operator++() { if (k == 0) { t = std::numeric_limits<uint32_t>::max(); } else { uint32_t y = t + _blsi_u32(t); // t + (-t & t) t = y | ((y ^ t) >> _tzcnt_u32(t << 2)); } } auto operator!=(std::nullptr_t) const { return t < n; } }; uint32_t s, k; all_subset_k(uint32_t s, uint32_t k) : s(s), k(k) { assert(s != std::numeric_limits<uint32_t>::max()); } static all_subset_k nCk(uint32_t n, uint32_t k) { return all_subset_k((uint32_t(1) << n) - 1, k); } auto begin() { return all_subset_k_iter(s, k); } auto end() { return nullptr; } }; struct all_subset_k_64 { struct all_subset_k_iter_64 { const uint64_t n, s; const uint32_t k; uint64_t t; __attribute__((target("avx2"))) all_subset_k_iter_64(uint64_t s, uint32_t k) : n(uint64_t(1) << _mm_popcnt_u64(s)), s(s), k(k), t((uint64_t(1) << k) - 1) {} __attribute__((target("bmi2"))) auto operator*() const { return _pdep_u64(t, s); } __attribute__((target("bmi"))) auto operator++() { if (k == 0) { t = std::numeric_limits<uint64_t>::max(); } else { uint64_t y = t + _blsi_u64(t); t = y | ((y ^ t) >> _tzcnt_u64(t << 2)); } } auto operator!=(std::nullptr_t) const { return t < n; } }; uint64_t s; uint32_t k; all_subset_k_64(uint64_t s, uint32_t k) : s(s), k(k) { assert(s != std::numeric_limits<uint64_t>::max()); } auto begin() { return all_subset_k_iter_64(s, k); } auto end() { return nullptr; } }; struct all_setbit { struct all_setbit_iter { uint32_t s; all_setbit_iter(uint32_t s) : s(s) {} __attribute__((target("bmi"))) auto operator*() { return _tzcnt_u32(s); } __attribute__((target("bmi"))) auto operator++() { s = __blsr_u32(s); } auto operator!=(std::nullptr_t) { return s; } }; uint32_t s; all_setbit(uint32_t s) : s(s) {} auto begin() { return all_setbit_iter(s); } auto end() { return nullptr; } }; struct all_setbit_64 { struct all_setbit_iter_64 { uint64_t s; all_setbit_iter_64(uint64_t s) : s(s) {} __attribute__((target("bmi"))) auto operator*() { return _tzcnt_u64(s); } __attribute__((target("bmi"))) auto operator++() { s = __blsr_u64(s); } auto operator!=(std::nullptr_t) { return s; } }; uint64_t s; all_setbit_64(uint64_t s) : s(s) {} auto begin() { return all_setbit_iter_64(s); } auto end() { return nullptr; } }; } // namespace suisen #line 11 "library/graph/minmax_floyd_warshall.hpp" namespace suisen { // Calculates D[i][j] := min{ max{ cost(e) | e in p } | p is an i-j path } in O(N^3/w) time. template <typename T, typename Compare = std::less<T>> std::vector<std::vector<T>> minmax_floyd_warshall(const std::vector<std::vector<T>>& cost_matrix, Compare comp = {}) { constexpr int B = 64; constexpr int LOG_B = 6; constexpr int MASK_B = B - 1; const int n = cost_matrix.size(), m = (n + B - 1) >> LOG_B; std::vector G(n, std::vector<uint64_t>(m)), rG(n, std::vector<uint64_t>(m)); std::vector res(n, std::vector<T>(n)); using E = std::tuple<T, int, int>; std::vector<E> edges(n * n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { edges[i * n + j] = { cost_matrix[i][j], i, j }; } std::sort(edges.begin(), edges.end(), [&comp](const E& e1, const E& e2) { return comp(std::get<0>(e1), std::get<0>(e2)); }); // Add edges in ascending order of their costs. for (const auto& [cost_, u, v] : edges) { const T& cost = cost_; auto add_edge = [&](int u, int v) { const int u_hi = u >> LOG_B, u_lo = u & MASK_B; const int v_hi = v >> LOG_B, v_lo = v & MASK_B; if ((G[u][v_hi] >> v_lo) & 1) { // already reachable return false; } res[u][v] = cost; G[u][v_hi] |= uint64_t(1) << v_lo; rG[v][u_hi] |= uint64_t(1) << u_lo; return true; }; auto rec = [&](auto rec, int u, int v) -> void { for (int i = 0; i < m; ++i) { // if (u ---> v) and (v ---> w) and (u -/-> w): add (u ---> w) if (uint64_t s = G[v][i] & ~G[u][i]) { const int w_hi = i << LOG_B; for (const int j : all_setbit_64(s)) add_edge(u, w_hi | j); for (const int j : all_setbit_64(s)) rec(rec, u, w_hi | j); } // if (w ---> u) and (u ---> v) and (w -/-> v): add (w ---> v) if (uint64_t s = rG[u][i] & ~rG[v][i]) { const int w_hi = i << LOG_B; for (const int j : all_setbit_64(s)) add_edge(w_hi | j, v); for (const int j : all_setbit_64(s)) rec(rec, w_hi | j, v); } } }; if (add_edge(u, v)) { rec(rec, u, v); } } return res; } } // namespace suisen #line 6 "test/src/graph/minmax_floyd_warshall/abc287_h.test.cpp" constexpr int inf = std::numeric_limits<int>::max() / 2; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<std::vector<int>> g(n, std::vector<int>(n, inf)); for (int i = 0; i < m; ++i) { int u, v; std::cin >> u >> v; --u, --v; g[u][v] = std::max(u, v) + 1; } std::vector<std::vector<int>> ans = suisen::minmax_floyd_warshall(g); int q; std::cin >> q; for (int i = 0; i < q; ++i) { int s, t; std::cin >> s >> t; --s, --t; std::cout << (ans[s][t] == inf ? -1 : ans[s][t]) << '\n'; } }