test/data_structures/consistent_trading.test.cpp

• View this file on GitHub
• Last update: 2026-02-06 17:15:57+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Summer/2971

Depends on

• data_structures/potentialized_rollback_dsu.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Summer/2971"

#include "data_structures/potentialized_rollback_dsu.hpp"
#include <bits/stdc++.h>

using i64 = long long;
using i128 = __int128;

struct A {
    static A op(A a, A b) { return {modmul(a.val, b.val)}; }
    static A e() { return {1}; }
    static A inv(A x) { return {modpow(x.val, mod - 2)}; }
    static i64 modmul(i64 a, i64 b) { return i64(i128(a) * b % mod); }
    static i64 modpow(i64 x, i64 n) {
        i64 r = 1;
        while (n) {
            if (n & 1) {
                r = modmul(r, x);
            }
            x = modmul(x, x);
            n >>= 1;
        }
        return r;
    }
    bool operator==(const A &other) const { return val == other.val; }
    i64 val;
    inline static i64 mod = (1LL << 61) - 1;
};

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, M;
    std::cin >> N >> M;
    PotentializedRollbackDSU<A> dsu(N);
    for (auto i = 0; i < M; ++i) {
        int v, u, x;
        std::cin >> v >> u >> x;
        --u, --v;
        dsu.merge(u, v, A{x});
    }
    auto ans = dsu.is_valid() ? "Yes" : "No";
    std::cout << ans << "\n";
}

#line 1 "test/data_structures/consistent_trading.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Summer/2971"

#line 1 "data_structures/potentialized_rollback_dsu.hpp"



#include <algorithm>
#include <cassert>
#include <tuple>
#include <vector>

// A is an abelian group
template <typename A> struct PotentializedRollbackDSU {
    explicit PotentializedRollbackDSU(int n)
        : n_(n), valid_(true), parent_or_size_(n, -1), potential_(n, A::e()) {}
    int leader(int u) const { return parent_or_size_[u] < 0 ? u : leader(parent_or_size_[u]); }
    // returns p_u
    A potential(int u) const {
        return parent_or_size_[u] < 0 ? A::e()
                                      : A::op(potential_[u], potential(parent_or_size_[u]));
    }
    // returns p_v - p_u
    A diff(int u, int v) const {
        auto p_u = potential(u);
        auto p_v = potential(v);
        return A::op(p_v, A::inv(p_u));
    }
    // returns history accumulation count for offline dynamic connectivity
    // p_u + w = p_v
    int merge(int u, int v, A w) {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        auto p_v = A::op(A::op(potential(u), w), A::inv(potential(v)));
        u = leader(u);
        v = leader(v);
        if (u == v) {
            history_.emplace_back(-1, 0, valid_);
            if (!(p_v == A::e())) {
                valid_ = false;
            }
            return 1;
        }
        // insert tree v into tree u
        if (-parent_or_size_[u] < -parent_or_size_[v]) {
            std::swap(u, v);
            p_v = A::inv(p_v);
        }
        history_.emplace_back(v, parent_or_size_[v], valid_);
        parent_or_size_[u] += parent_or_size_[v];
        parent_or_size_[v] = u;
        potential_[v] = p_v;
        return 1;
    }
    bool same(int u, int v) const {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        return leader(u) == leader(v);
    }
    int size(int u) const {
        assert(0 <= u && u < n_);
        return -parent_or_size_[leader(u)];
    }
    void rollback() {
        assert(!history_.empty());
        auto [v, size, valid] = history_.back();
        if (~v) {
            auto u = parent_or_size_[v];
            parent_or_size_[v] = size;
            parent_or_size_[u] -= size;
            potential_[v] = A::e();
        } else {
            valid_ = valid;
        }
        history_.pop_back();
    }
    void rollback(int count) {
        for (auto i = 0; i < count; ++i) {
            rollback();
        }
    }
    bool is_valid() const { return valid_; }

private:
    int n_;
    bool valid_;
    std::vector<int> parent_or_size_;
    std::vector<A> potential_;
    std::vector<std::tuple<int, int, bool>> history_;
};


#line 4 "test/data_structures/consistent_trading.test.cpp"
#include <bits/stdc++.h>

using i64 = long long;
using i128 = __int128;

struct A {
    static A op(A a, A b) { return {modmul(a.val, b.val)}; }
    static A e() { return {1}; }
    static A inv(A x) { return {modpow(x.val, mod - 2)}; }
    static i64 modmul(i64 a, i64 b) { return i64(i128(a) * b % mod); }
    static i64 modpow(i64 x, i64 n) {
        i64 r = 1;
        while (n) {
            if (n & 1) {
                r = modmul(r, x);
            }
            x = modmul(x, x);
            n >>= 1;
        }
        return r;
    }
    bool operator==(const A &other) const { return val == other.val; }
    i64 val;
    inline static i64 mod = (1LL << 61) - 1;
};

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, M;
    std::cin >> N >> M;
    PotentializedRollbackDSU<A> dsu(N);
    for (auto i = 0; i < M; ++i) {
        int v, u, x;
        std::cin >> v >> u >> x;
        --u, --v;
        dsu.merge(u, v, A{x});
    }
    auto ans = dsu.is_valid() ? "Yes" : "No";
    std::cout << ans << "\n";
}

Back to top page