12232

12232 - Exclusive-OR

题目大意是可以设定一个点Xp=v，或者Xp^Xq=v，然后查询Xa^Xb^Xc...等于多少。

由于异或操作跟判连通性很类似，这里可以使用并查集来解决，对于Xp^Xq=v先判断Xp和Xq是否来自一颗树，若是来自一个棵树，则判相容性，否则连接这两棵树，而Xp=v是用来lock一棵树的，当一棵树未被lock时，这颗树中的所有值都不确定，当lock之后，就可以确定这颗树的所有值了。而最后求Xa^Xb^Xc...时，先按树进行分类，对于lock的树的X直接求解，都与非lock的树，若有偶数个则可以求解，否则得不到固定的值，算法应该没有问题，可是AC不了，不好debug，下面是代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <sstream>
using namespace std;

const int MAXN = 20005;

int f[MAXN], p[MAXN], xor_value[MAXN];

int find_father(int i) {
    if (f[i] == i) {
        xor_value[i] = 0;
        return i;
    } else {
        int root = find_father(f[i]);
        xor_value[i] ^= xor_value[f[i]];
        return f[i] = root;
    }
}

int insert(vector<int> v) {
    if (v.size() == 2) {
        int root = find_father(v[0]);
        if (p[root] == -1 || p[root] == (xor_value[v[0]] ^ v[1])) {
            p[root] = xor_value[v[0]] ^ v[1];
        } else {
            return -2;
        }
    } else {
        int root0 = find_father(v[0]);
        int root1 = find_father(v[1]);
        if (root0 == root1) {
            if ((xor_value[v[0]] ^ xor_value[v[1]]) != v[2]) {
                return -2;
            }
        } else {
            f[root1] = root0;
            xor_value[root1] = xor_value[v[0]] ^ xor_value[v[1]] ^ v[2];
            if (p[root1] != -1) {
                int tmp = p[root1] ^ xor_value[root1];
                if (p[root0] == -1 || p[root0] == tmp) {
                    p[root0] = tmp;
                } else {
                    return -2;
                }
            }
        }
    }
    return -3;
}

int query(vector<int> v) {
    map<int, vector<int> > kind;
    for (int i = 1; i < v.size(); i++) {
        vector<int> zero;
        int father = find_father(v[i]);
        if (kind.find(father) == kind.end()) {
            kind[father] = zero;
        }
        kind[father].push_back(v[i]);
    }
    int res = 0;
    for (map<int, vector<int> >::iterator it = kind.begin(); it != kind.end(); it++) {
        vector<int> son = it->second;
        if (p[it->first] != -1) {
            for (int i = 0; i < son.size(); i++) {
                res ^= (p[it->first] ^ xor_value[son[i]]); 
            } 
        } else {
            if (son.size() & 1) {
                return -1;
            } else {
                for (int i = 0; i < son.size(); i += 2) {
                    res ^= (xor_value[son[i]] ^ xor_value[son[i + 1]]);
                }    
            }
        }
    }
    return res;
}

int main() {
    int n, q, cc = 0;
    while (scanf("%d%d", &n, &q)) {
        if (n == 0 && q == 0) break;
        getchar();
        printf("Case %d:
", ++cc);
        for (int i = 0; i < n; i++) f[i] = i;
        memset(p, -1, sizeof(p));
        int facts = 0;
        bool bad = false;
        for (int c = 0; c < q; c++) {
            int t;
            char arg[1000], cmd;
            vector<int> v;

            gets(arg);

            if (bad) continue;

            stringstream ss(arg);
            
            ss >> cmd;
            while (ss >> t) v.push_back(t);
            int res;
            if (cmd == 'I') {
                res = insert(v);  
                facts++;
            } else if (cmd == 'Q') {
                res = query(v);
            }
            if (res == -1) printf("I don't konw.
");
            else if (res == -2) {
                printf("The first %d facts are conflicting.
", facts);
                bad = true;
            } else if (res >= 0) printf("%d
", res);
        }
        printf("
");
    }
}