异或图

题目

现在有 个点构成的点集 ，每个点有点权 。想用这 个点构造 个无向图 。
对于第 个无向图，牛妹指定了一个参数 。牛妹规定 当且仅当 ，其中 表示二进制按位异或运算。
对于第 个无向图，求 到 的最短路径长度，。

解题思路

对于任意 3 个整数 ，若 ，则有 ，。

1. 如果 a[x] ^ k == a[y]，表示 (x,y) 是无向图中的一个边，距离为 1。
2. 如果上述条件不成立，判断 a[x] ^ k 是否存在，如果不存在，表示这个点是独立的，返回 -1。
   如果存在，判断 a[x] 与 a[y] 是否相等，如果相等，表示点 x 和 y 都与权值为 a[x]^k 的点相邻，所以距离为 2。
3. 以上条件均不成立，返回 -1。

C++代码

#include<cstdio>
#include<vector>
using namespace std;

int exist[1048576];

int main(){
    int n, q;
    scanf("%d%d", &n, &q);
    vector<int> a(n+1);
    for(int i=1; i<=n; ++i){
        scanf("%d", &a[i]);
        exist[a[i]] = 1;
    }
    int k, x, y;
    for(int i=0; i<q; ++i){
        scanf("%d%d%d", &k, &x, &y);
        int ax = a[x];
        int ay = a[y];
        int b = ax ^ k;
        int ans = -1;
        if(ay==b)
            ans = 1;
        else if(exist[b]==1 && ax==ay)
            ans = 2;
        printf("%d\n", ans);
    }
    return 0;
}