HZOJ-72：猜拳

 

题目描述

​ 在一次聚会中，每人拿着一张印有石头、剪刀、布的卡片，每个人具体拿得是哪种卡片不得而知。

​ 现在告诉你某些人之间的胜负关系，并会询问某两个人之间的对战结果，人按照从 11 到 n� 编号。

​ 对于每个询问，请给出正确的回答： Win(胜)、Loss(负)、Tie(平)���(胜)、����(负)、���(平)

---

输入

第一行输入两个整数 n,m(1≤n≤10000，3≤m≤10000)�,�(1≤�≤10000，3≤�≤10000)，分别代表人数和信息数量。

接下来 m� 行，每行三个整 a,b,c（a∈[1,2], 1≤b,c≤n）�,�,�（�∈[1,2], 1≤�,�≤�）

1. 当 a=1�=1 时，代表新增一条已知信息，表示 b, c�, � 对战中 b� 胜
2. 当 a=2�=2 时，代表根据以上信息，询问 b,c�,� 对战中 b​�​ 的结果

如果出现某条新增的信息与之前的信息发生冲突，就忽略此条信息。

输出

对于每个 a=2�=2 的操作，输出 Win、Loss、Tie���、����、��� 或 Unknown������� 代表对战双方的结果。

---

样例输入

6 6
1 1 2
2 1 3
1 2 4
1 4 3
2 1 3
2 4 1

样例输出

Unknown
Tie
Win

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class WeightedUnionSet {
public :
	WeightedUnionSet(int n) : fa(n + 1), val(n + 1) {
		for (int i = 0; i <= n; i++) {
			fa[i] = i;
			val[i] = 0;
		}
	}
	int get(int x) {
		if (fa[x] == x) return x;
		int root = get(fa[x]);
		val[x] = (val[x] + val[fa[x]]) % 3;
		return fa[x] = root;
	}
	void merge(int a, int b ,int t) {
		int aa = get(a), bb = get(b);
		if (aa == bb) return;
		fa[aa] = bb;
		val[aa] = (t - val[a] + val[b] + 3) % 3;
		return;
	}
	vector<int> fa, val;
};
int main() {
	int n, m;
	cin >> n >> m;
	WeightedUnionSet u(n);
	for (int i = 0, a, b, c; i < m; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			u.merge(b, c, 2);
		}
		else {
			if (u.get(b) != u.get(c)) {
				cout << "Unknown" << endl;
			}
			else {
				switch ((u.val[b] - u.val[c] + 3) % 3) {
				case 0: cout << "Tie" << endl; break;
				case 1: cout << "Loss" << endl; break;
				case 2: cout << "Win" << endl; break;
				}
			}
		}
	}
	return 0;
}