結果

問題 No.1420 国勢調査 (Easy)
コンテスト
ユーザー kwm_t
提出日時 2021-03-09 19:52:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,850 bytes
コンパイル時間 1,686 ms
コンパイル使用メモリ 170,960 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 12:33:15
合計ジャッジ時間 7,800 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7 WA * 18 RE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
//#include "atcoder/all"
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"

template<class Abel> struct UnionFind {
	vector<int> par;
	vector<int> rank;
	vector<Abel> diff_weight;

	UnionFind(int n = 1, Abel SUM_UNITY = 0) { init(n, SUM_UNITY); }

	void init(int n = 1, Abel SUM_UNITY = 0) {
		par.resize(n); rank.resize(n); diff_weight.resize(n);
		for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
	}

	int root(int x) {
		if (par[x] == x) { return x; }
		int r = root(par[x]);
		diff_weight[x] ^= diff_weight[par[x]];//★編集★
		par[x] = r;
		return r;
	}

	Abel weight(int x) {
		root(x);
		return diff_weight[x];
	}

	bool issame(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y, Abel w) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) {
			if (w != (weight(x) ^ weight(y))) {
				return false;
			}
			return true;
		}
		par[ry] = x;
		diff_weight[ry] = w ^ diff_weight[y];
		return true;
	}

	Abel diff(int x, int y) {
		return weight(y) ^ weight(x);//★編集★
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, M;
	cin >> N >> M;
	UnionFind<int> uf(N);
	rep(i, N) {
		int a, b, y;
		cin >> a >> b >> y;
		a--;
		b--;
		if (!uf.merge(a, b, y)) {
			cout << -1 << endl;
			return 0;
		}
	}
	rep(i, N) {
		cout << uf.diff_weight[i] << endl;
	}
	return 0;
}
0