Test/AtCoder/arc165_c.test.cpp

View this file on GitHub
Last update: 2023-09-24 02:53:58+09:00
Problem: https://atcoder.jp/contests/arc165/tasks/arc165_c

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/arc165/tasks/arc165_c"

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/Utility/BinarySearch.hpp"

#include <iostream>

int main() {
    using namespace zawa;
    u32 n, m; std::cin >> n >> m;
    std::vector g(n, std::vector<std::pair<u32, u32>>{});
    for (u32 _{} ; _ < m ; _++) {
        u32 a, b, w; std::cin >> a >> b >> w;
        a--; b--;
        g[a].emplace_back(w, b);
        g[b].emplace_back(w, a);
    }
    for (auto& adj : g) std::sort(adj.begin(), adj.end());

    auto f{[&](u32 X) -> bool {
        std::vector<i32> col(n, -1);
        auto rec{[&](auto rec, u32 v, u32 c) -> bool {
            col[v] = c;
            for (auto [w, x] : g[v]) {
                if (w >= X) break;
                if (col[x] == -1 and !rec(rec, x, c ^ 1)) return false;
                if (col[x] == (i32)c) return false;
            }
            return true;
        }};
        for (u32 i{} ; i < n ; i++) if (col[i] == -1 and !rec(rec, i, 0))
            return false;
        for (u32 i{} ; i < n ; i++) if (g[i].size() > 1) {
            if (g[i][0].first + g[i][1].first < X) return false;
        }
        return true;
    }};

    u32 ans{ BinarySearch(u32{}, (u32)2e9 + 1, f) };
    std::cout << ans << std::endl;
}

#line 1 "Test/AtCoder/arc165_c.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/arc165/tasks/arc165_c"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Utility/BinarySearch.hpp"

#line 4 "Src/Utility/BinarySearch.hpp"

#include <cmath>
#include <functional>
#include <type_traits>
#include <utility>

namespace zawa {

namespace internal {

template <class T>
T MidPoint(T a, T b) {
    if (a > b) std::swap(a, b);
    return a + ((b - a) >> 1);
}

template <class T>
T Abs(T a, T b) {
    return (a >= b ? a - b : b - a);
}

} // namespace zawa::internal

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f) {
    static_assert(std::is_integral_v<T>, "T must be integral type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    while (internal::Abs(ok, ng) > 1) {
        T mid{ internal::MidPoint(ok, ng) };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f, u32 upperLimit) {
    static_assert(std::is_signed_v<T>, "T must be signed arithmetic type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    for (u32 _{} ; _ < upperLimit ; _++) {
        T mid{ (ok + ng) / (T)2 };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

} // namespace zawa
#line 5 "Test/AtCoder/arc165_c.test.cpp"

#include <iostream>

int main() {
    using namespace zawa;
    u32 n, m; std::cin >> n >> m;
    std::vector g(n, std::vector<std::pair<u32, u32>>{});
    for (u32 _{} ; _ < m ; _++) {
        u32 a, b, w; std::cin >> a >> b >> w;
        a--; b--;
        g[a].emplace_back(w, b);
        g[b].emplace_back(w, a);
    }
    for (auto& adj : g) std::sort(adj.begin(), adj.end());

    auto f{[&](u32 X) -> bool {
        std::vector<i32> col(n, -1);
        auto rec{[&](auto rec, u32 v, u32 c) -> bool {
            col[v] = c;
            for (auto [w, x] : g[v]) {
                if (w >= X) break;
                if (col[x] == -1 and !rec(rec, x, c ^ 1)) return false;
                if (col[x] == (i32)c) return false;
            }
            return true;
        }};
        for (u32 i{} ; i < n ; i++) if (col[i] == -1 and !rec(rec, i, 0))
            return false;
        for (u32 i{} ; i < n ; i++) if (g[i].size() > 1) {
            if (g[i][0].first + g[i][1].first < X) return false;
        }
        return true;
    }};

    u32 ans{ BinarySearch(u32{}, (u32)2e9 + 1, f) };
    std::cout << ans << std::endl;
}