test/yukicoder/1420.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://yukicoder.me/problems/no/1420

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1420"
#define ERROR 1 // Check only whether the answer is -1 or not (by hitonanode)
#include <bits/stdc++.h>

#include "library/algebra/group/Xor.hpp"
#include "library/datastructure/unionfind/PotentialUnionFind.hpp"

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

    int n, m;
    std::cin >> n >> m;
    PotentialUnionFind<GroupXor<int>> UF(n);
    while (m--) {
        int a, b, y;
        std::cin >> a >> b >> y;
        a--;
        b--;
        if (!UF.merge(a, b, y)) {
            std::cout << -1 << "\n";
            return 0;
        }
    }
    for (int i = 0; i < n; i++)
        std::cout << UF.from_root(i).second << "\n";
}

#line 1 "test/yukicoder/1420.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1420"
#define ERROR 1 // Check only whether the answer is -1 or not (by hitonanode)
#include <bits/stdc++.h>

#line 1 "library/algebra/group/Xor.hpp"
template<typename X>
struct GroupXor {
  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){ y^=x; }
  static constexpr X inverse(const X &x) noexcept { return x; }
  static constexpr X power(const X &x, long long n) noexcept { return (n&1?x:0); }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#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 7 "test/yukicoder/1420.test.cpp"

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

    int n, m;
    std::cin >> n >> m;
    PotentialUnionFind<GroupXor<int>> UF(n);
    while (m--) {
        int a, b, y;
        std::cin >> a >> b >> y;
        a--;
        b--;
        if (!UF.merge(a, b, y)) {
            std::cout << -1 << "\n";
            return 0;
        }
    }
    for (int i = 0; i < n; i++)
        std::cout << UF.from_root(i).second << "\n";
}