【HDOJ】3234 Exclusive-OR

并查集。对于对元素赋值操作，更改为I p n v。令val[n]=0（任何数与0异或仍为原值）。
考虑fa[x] = fx, fa[y] = fy。
如果使得fa[fx] = fy, 那么val[fx] = TrueVal[fx] ^ TrueVal[fy] = (val[x] ^ TrueVal[x]) ^ (val[y] ^ TrueVal[y]) = (val[x] ^ val[y]) ^ (TrueVal[x] ^ TrueVal[y]) = val[x] ^ val[y] ^ z。
同时每次find时，也需要更新val(因为fa不同了)。
对于Query操作，有效的Query为cnt为偶数或者root为n。
输出样例有问题，每个case后有空行。

 /* 3234 */

 #include <iostream>

 #include <string>

 #include <map>

 #include <queue>

 #include <set>

 #include <stack>

 #include <vector>

 #include <deque>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <ctime>

 #include <cstring>

 #include <climits>

 #include <cctype>

 #include <cassert>

 #include <functional>

 #include <iterator>

 #include <iomanip>

 using namespace std;

 //#pragma comment(linker,"/STACK:102400000,1024000")

 #define sti                set<int>

 #define stpii            set<pair<int, int> >

 #define mpii            map<int,int>

 #define vi                vector<int>

 #define pii                pair<int,int>

 #define vpii            vector<pair<int,int> >

 #define rep(i, a, n)     for (int i=a;i<n;++i)

 #define per(i, a, n)     for (int i=n-1;i>=a;--i)

 #define clr                clear

 #define pb                 push_back

 #define mp                 make_pair

 #define fir                first

 #define sec                second

 #define all(x)             (x).begin(),(x).end()

 #define SZ(x)             ((int)(x).size())

 #define lson            l, mid, rt<<1

 #define rson            mid+1, r, rt<<1|1

 const int maxn = 2e4+;

 const int maxk = ;

 int fa[maxn], val[maxn];

 int P[maxk], K;

 bool visit[maxk];

 int n;

 int find(int x) {

     if (fa[x] == x)

         return x;

     int tmp = fa[x];

     fa[x] = find(fa[x]);

     val[x] ^= val[tmp];

     return fa[x];

 }

 void init() {

     rep(i, , n+) {

         val[i] = ;

         fa[i] = i;

     }

 }

 bool merge(int u, int v, int x) {

     int fu = find(u);

     int fv = find(v);

     if (fu == fv) {

         return (val[u]^val[v]) == x;

     }

     if (fu == n)    swap(fu, fv);

     fa[fu] = fv;

     val[fu] = val[u]^val[v]^x;

     return true;

 }

 int Query() {

     int f, c;

     int ret = ;

     memset(visit, false, sizeof(visit));

     rep(i, , K)

         find(P[i]);

     rep(i, , K) {

         if (visit[i])

             continue;

         f = fa[P[i]];

         c = ;

         rep(j, i, K) {

             if (!visit[j] && fa[P[j]]==f) {

                 ++c;

                 visit[j] = true;

                 ret ^= val[P[j]];

             }

         }

         if (f!=n && (c&))

             return -;

     }

     return ret;

 }

 int main() {

     ios::sync_with_stdio(false);

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         freopen("data.out", "w", stdout);

     #endif

     int q;

     int isn;

     int a[], c;

     int u, v, x;

     int ans;

     char cmd[], line[];

     bool flag;

     int t = ;

     while (scanf("%d %d", &n, &q)!=EOF && (n||q)) {

         printf("Case %d:\n", ++t);

         init();

         flag = true;

         isn = ;

         while (q--) {

             scanf("%s%*c", cmd);

             if (cmd[] == 'I') {

                 gets(line);

             } else {

                 scanf("%d", &K);

                 rep(i, , K)

                     scanf("%d", &P[i]);

             }

             if (!flag)

                 continue;

             if (cmd[] == 'I') {

                 int len = strlen(line);

                 ++isn;

                 c = ;

                 a[c] = ;

                 rep(i, , len) {

                     if (line[i] == ' ') {

                         ++c;

                         a[c] = ;

                     } else {

                         a[c] = *a[c] + line[i]-'';

                     }

                 }

                 if (c == ) {

                     u = a[];

                     v = n;

                     x = a[];

                 } else {

                     u = a[];

                     v = a[];

                     x = a[];

                 }

                 flag = merge(u, v, x);

                 if (!flag) {

                     printf("The first %d facts are conflicting.\n", isn);

                 }

             } else {

                 ans = Query();

                 if (ans == -) {

                     puts("I don't know.");

                 } else {

                     printf("%d\n", ans);

                 }

             }

         }

         putchar('\n');

     }

     #ifndef ONLINE_JUDGE

         printf("time = %d.\n", (int)clock());

     #endif

     return ;

 }

巴特西

【HDOJ】3234 Exclusive-OR

最新文章

热门文章