cp-library-cpp

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

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/graph/minmax_floyd_warshall/abc287_h.test.cpp

Depends on

Code

#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';
    }
}
Back to top page