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