:heavy_check_mark: test/AOJ/2971.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2971"
#include <bits/stdc++.h>

#include "library/algebra/group/Multiply.hpp"
#include "library/datastructure/unionfind/PotentialUnionFind.hpp"
#include "library/mod/Modint.hpp"
using ll = long long;
using mint1 = Mint<ll, 998244341>;
using mint2 = Mint<ll, 998244389>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;
    PotentialUnionFind<GroupMultiply<mint1>> uf1(n);
    PotentialUnionFind<GroupMultiply<mint2>> uf2(n);

    while (m--) {
        int a, b, c;
        std::cin >> a >> b >> c;
        a--;
        b--;
        if (!uf1.merge(a, b, c) || !uf2.merge(a, b, c)) {
            std::cout << "No\n";
            return 0;
        }
    }
    std::cout << "Yes\n";
}
#line 1 "test/AOJ/2971.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2971"
#include <bits/stdc++.h>

#line 1 "library/algebra/group/Multiply.hpp"
template<typename X,bool COMMUTE=true>
struct GroupMultiply{
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x * y; }
  static constexpr void Rchop(X&x, const X&y){ x*=y; }
  static constexpr void Lchop(const X&x, X&y){ 
    if constexpr(COMMUTE){ y*=x; }
    else{ y=x*y;} 
  }
  static constexpr X inverse(const X &x) noexcept { return X(1)/x; }
  static constexpr X power(const X &x, long long n) noexcept { return x.pow(n); }
  static constexpr X unit() { return X(1); }
  static constexpr bool commute = COMMUTE;
};
#line 2 "library/datastructure/unionfind/PotentialUnionFind.hpp"
template <typename AbelGroup> class PotentialUnionFind {
    using T = typename AbelGroup::value_type;
    int n, num;
    std::vector<int> sz, parent;
    std::vector<T> potential; // parent[x] を基準とした時の x の値
  public:
    PotentialUnionFind() = default;
    PotentialUnionFind(int n)
        : n(n), num(n), sz(n, 1), parent(n, 0),
          potential(n, AbelGroup::unit()) {
        assert(AbelGroup::commute);
        std::iota(parent.begin(), parent.end(), 0);
    }

    std::pair<int, T> from_root(int x) {
        if (x == parent[x])
            return {x, AbelGroup::unit()};
        auto [r, add] = from_root(parent[x]);
        parent[x] = r;
        AbelGroup::Rchop(potential[x], add);
        return {r, potential[x]};
    }

    int leader(int x) { return from_root(x).first; }

    bool same(int x, int y) {
        assert(0 <= x and x < n and 0 <= y and y < n);
        return leader(x) == leader(y);
    }

    bool merge(int x, int y, T d) {
        // potential[y]-potential[x]=d にする
        // 矛盾する場合は変更はせず false を返す
        assert(0 <= x and x < n and 0 <= y and y < n);
        auto [rx, dx] = from_root(x);
        auto [ry, dy] = from_root(y);
        AbelGroup::Rchop(d, dx);
        AbelGroup::Rchop(d, AbelGroup::inverse(dy));
        if (rx == ry)
            return d == AbelGroup::unit();
        if (sz[rx] < sz[ry]) {
            std::swap(rx, ry);
            d = AbelGroup::inverse(d);
        }
        sz[rx] += sz[ry];
        parent[ry] = rx;
        potential[ry] = d;
        num--;
        return true;
    }

    std::optional<T> diff(int x, int y) {
        // x を基準とする
        auto [rx, dx] = from_root(x);
        auto [ry, dy] = from_root(y);
        if (rx != ry)
            return std::nullopt;
        return AbelGroup::op(dy, AbelGroup::inverse(dx));
    }

    int size(const int x) {
        assert(0 <= x and x < n);
        return sz[leader(x)];
    }

    int count() const { return num; }
};
#line 2 "library/math/ExtraGCD.hpp"
using ll = long long;
std::pair<ll, ll> ext_gcd(ll a, ll b) {
    if (b == 0)
        return {1, 0};
    auto [X, Y] = ext_gcd(b, a % b);
    // bX + (a%b)Y = gcd(a,b)
    // a%b = a - b(a/b)
    // ∴ aY + b(X-(a/b)Y) = gcd(a,b)
    ll x = Y, y = X - (a / b) * Y;
    return {x, y};
}
#line 3 "library/mod/Modint.hpp"
template <typename T, T MOD = 998244353> struct Mint {
    inline static constexpr T mod = MOD;
    T v;
    Mint() : v(0) {}
    Mint(signed v) : v(v) {}
    Mint(long long t) {
        v = t % MOD;
        if (v < 0)
            v += MOD;
    }

    static Mint raw(int v) {
        Mint x;
        x.v = v;
        return x;
    }

    Mint pow(long long k) const {
        Mint res(1), tmp(v);
        while (k) {
            if (k & 1)
                res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }

    static Mint add_identity() { return Mint(0); }
    static Mint mul_identity() { return Mint(1); }

    // Mint inv()const{return pow(MOD-2);}
    Mint inv() const { return Mint(ext_gcd(v, mod).first); }

    Mint &operator+=(Mint a) {
        v += a.v;
        if (v >= MOD)
            v -= MOD;
        return *this;
    }
    Mint &operator-=(Mint a) {
        v += MOD - a.v;
        if (v >= MOD)
            v -= MOD;
        return *this;
    }
    Mint &operator*=(Mint a) {
        v = 1LL * v * a.v % MOD;
        return *this;
    }
    Mint &operator/=(Mint a) { return (*this) *= a.inv(); }

    Mint operator+(Mint a) const { return Mint(v) += a; }
    Mint operator-(Mint a) const { return Mint(v) -= a; }
    Mint operator*(Mint a) const { return Mint(v) *= a; }
    Mint operator/(Mint a) const { return Mint(v) /= a; }
#define FRIEND(op)                                                             \
    friend Mint operator op(int a, Mint b) { return Mint(a) op b; }
    FRIEND(+);
    FRIEND(-);
    FRIEND(*);
    FRIEND(/);
#undef FRIEND
    Mint operator+() const { return *this; }
    Mint operator-() const { return v ? Mint(MOD - v) : Mint(v); }

    bool operator==(const Mint a) const { return v == a.v; }
    bool operator!=(const Mint a) const { return v != a.v; }

    static Mint comb(long long n, int k) {
        Mint num(1), dom(1);
        for (int i = 0; i < k; i++) {
            num *= Mint(n - i);
            dom *= Mint(i + 1);
        }
        return num / dom;
    }

    friend std::ostream &operator<<(std::ostream &os, const Mint &m) {
        os << m.v;
        return os;
    }
    friend std::istream &operator>>(std::istream &is, Mint &m) {
        is >> m.v;
        m.v %= MOD;
        if (m.v < 0)
            m.v += MOD;
        return is;
    }
};
#line 7 "test/AOJ/2971.test.cpp"
using ll = long long;
using mint1 = Mint<ll, 998244341>;
using mint2 = Mint<ll, 998244389>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;
    PotentialUnionFind<GroupMultiply<mint1>> uf1(n);
    PotentialUnionFind<GroupMultiply<mint2>> uf2(n);

    while (m--) {
        int a, b, c;
        std::cin >> a >> b >> c;
        a--;
        b--;
        if (!uf1.merge(a, b, c) || !uf2.merge(a, b, c)) {
            std::cout << "No\n";
            return 0;
        }
    }
    std::cout << "Yes\n";
}
Back to top page