cp-documentation

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

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AtCoder/agc002_d.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
// #define PROBLEM "https://atcoder.jp/contests/agc002/tasks/agc002_d"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Utility/ParallelBinarySearch.hpp"
#include "../../Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"

/*
 * AGC002-D Stampl Rally
 * https://atcoder.jp/contests/agc002/submissions/63106870
 */

#include <algorithm>
#include <vector>

using namespace zawa;
int N, M, A[100010], B[100010], Q, X[100010], Y[100010], Z[100010];
void solve() {
    auto f = [&](auto a) {
        std::sort(a.begin(), a.end());
        std::vector<std::pair<bool, int>> res(a.size());
        DisjointSetUnion dsu(N);
        for (int i = 1, j = 0 ; i <= M ; i++) {
            dsu.merge(A[i], B[i]);
            assert(j == (int)a.size() or a[j].first >= i);
            while (j < (int)a.size() and a[j].first == i) {
                int id = a[j].second;
                int num = (int)dsu.size(X[id]) + (dsu.same(X[id], Y[id]) ? 0 : (int)dsu.size(Y[id]));
                bool ans = num >= Z[id];
                res[j++] = {ans, id};
            }
        }
        return res;
    };
    auto ans = ParallelBinarySearch(std::vector<int>(Q, M), std::vector<int>(Q, 0), f);
    for (int i = 0 ; i < Q ; i++) std::cout << ans[i] << '\n';
}
int main() {
#ifdef ATCODER
    SetFastIO();
    std::cin >> N >> M;
    for (int i = 1 ; i <= M ; i++) {
        std::cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }
    std::cin >> Q;
    for (int i = 0 ; i < Q ; i++) {
        std::cin >> X[i] >> Y[i] >> Z[i];
        X[i]--; Y[i]--;
    }
    solve();
#else
    std::cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/agc002_d.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
// #define PROBLEM "https://atcoder.jp/contests/agc002/tasks/agc002_d"

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

#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 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

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

#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

namespace zawa {

template <std::integral T, class F>
std::vector<T> ParallelBinarySearch(std::vector<T> oks, std::vector<T> ngs, F f) {
    assert(oks.size() == ngs.size());
    while (true) {
        std::vector<std::pair<T, usize>> remains; 
        std::vector<usize> inv(oks.size(), static_cast<usize>(-1));
        for (usize i = 0 ; i < oks.size() ; i++) if ((oks[i] >= ngs[i] ? oks[i] - ngs[i] : ngs[i] - oks[i]) > T{1}) {
            T mid = (oks[i]&ngs[i]) + ((oks[i]^ngs[i])>>1);
            inv[i] = remains.size();
            remains.push_back({mid, i});
        }
        if (remains.empty()) break;
        auto res = f(remains);
        assert(res.size() == remains.size());
        for (usize i = 0 ; i < res.size() ; i++) {
            T mid = remains[inv[res[i].second]].first;
            if (res[i].first) oks[res[i].second] = mid;
            else ngs[res[i].second] = mid;
            i++;
        }
    } 
    return oks;
}

} // namespace zawa
#line 2 "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"

#line 4 "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"

#include <algorithm>
#line 7 "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"
#include <numeric>
#line 10 "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"

namespace zawa {

class DisjointSetUnion {
public:
    DisjointSetUnion() = default;

    DisjointSetUnion(usize n) : n_{n}, comps_{n}, data_(n, -1) {
        data_.shrink_to_fit();
    }
    
    u32 leader(u32 v) {
        return data_[v] < 0 ? v : static_cast<u32>(data_[v] = leader(data_[v]));
    }

    bool same(u32 u, u32 v) {
        return leader(u) == leader(v);
    }

    bool merge(u32 u, u32 v) {
        assert(u < n_);
        assert(v < n_);
        u = leader(u);
        v = leader(v);
        if (u == v) return false;
        comps_--;
        if (data_[u] > data_[v]) std::swap(u, v);
        data_[u] += data_[v];
        data_[v] = u;
        return true;
    }

    inline usize size() const noexcept {
        return n_;
    }

    usize size(u32 v) {
        assert(v < n_);
        return static_cast<usize>(-data_[leader(v)]);
    }

    inline usize components() const noexcept {
        return comps_;
    }

    template <class T = usize>
    std::vector<std::vector<T>> enumerate() requires std::convertible_to<usize, T> {
        std::vector<std::vector<T>> res(n_);
        for (usize v{} ; v < n_ ; v++) {
            res[leader(v)].push_back(static_cast<T>(v));
        }
        std::erase_if(res, [](const auto& arr) -> bool { return arr.empty(); });
        return res;
    }

private:
    usize n_{}, comps_{};
    std::vector<i32> data_;
};

} // namespace zawa
#line 7 "Test/AtCoder/agc002_d.test.cpp"

/*
 * AGC002-D Stampl Rally
 * https://atcoder.jp/contests/agc002/submissions/63106870
 */

#line 15 "Test/AtCoder/agc002_d.test.cpp"

using namespace zawa;
int N, M, A[100010], B[100010], Q, X[100010], Y[100010], Z[100010];
void solve() {
    auto f = [&](auto a) {
        std::sort(a.begin(), a.end());
        std::vector<std::pair<bool, int>> res(a.size());
        DisjointSetUnion dsu(N);
        for (int i = 1, j = 0 ; i <= M ; i++) {
            dsu.merge(A[i], B[i]);
            assert(j == (int)a.size() or a[j].first >= i);
            while (j < (int)a.size() and a[j].first == i) {
                int id = a[j].second;
                int num = (int)dsu.size(X[id]) + (dsu.same(X[id], Y[id]) ? 0 : (int)dsu.size(Y[id]));
                bool ans = num >= Z[id];
                res[j++] = {ans, id};
            }
        }
        return res;
    };
    auto ans = ParallelBinarySearch(std::vector<int>(Q, M), std::vector<int>(Q, 0), f);
    for (int i = 0 ; i < Q ; i++) std::cout << ans[i] << '\n';
}
int main() {
#ifdef ATCODER
    SetFastIO();
    std::cin >> N >> M;
    for (int i = 1 ; i <= M ; i++) {
        std::cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }
    std::cin >> Q;
    for (int i = 0 ; i < Q ; i++) {
        std::cin >> X[i] >> Y[i] >> Z[i];
        X[i]--; Y[i]--;
    }
    solve();
#else
    std::cout << "Hello World\n";
#endif
}
Back to top page