#627030 (C++14) No.1420 国勢調査 (Easy)

• 問題: No.1420 国勢調査 (Easy)
• ユーザー: kwm_t
• 提出日時: 2021-03-09 19:52:47
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,850 bytes
• コンパイル時間: 1,567 ms
• コンパイル使用メモリ: 167,400 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-04-19 20:20:03
• 合計ジャッジ時間: 6,709 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	4 ms; 5,376 KB
testcase_13	WA	-
testcase_14	AC	5 ms; 5,376 KB
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	18 ms; 5,376 KB
testcase_28	AC	17 ms; 5,376 KB
testcase_29	AC	10 ms; 5,376 KB
testcase_30	AC	17 ms; 5,376 KB
testcase_31	AC	16 ms; 5,376 KB

ソースコード

#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;
}