1659E - AND-MEX Walk - CodeForces Solution

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define lowbit(x) ((x) & (-x))
#define PI acos(-1)
#define el "\n"
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int fa[35][N], is[35][N];

void init(int n) {
    for (int i = 0; i < 31; i ++) {
        for (int j = 1; j <= n; j ++) {
            fa[i][j] = j;
            is[i][j] = 0;
        }
    }
}

int find(int p, int x) {
    if (fa[p][x] == x) return x;
    else return fa[p][x] = find(p, fa[p][x]);
}

void merge(int p, int x, int y) {
    int fx = find(p, x), fy = find(p, y);
    if (fx == fy) return;
    fa[p][fx] = fy;
}   

vector<PII> G[N];

void solve() {
    int n, m;
    cin >> n >> m;
    init(n);
    for (int i = 1; i <= m; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});  
        for (int j = 0; j <= 30; j ++) {
            int x = (w >> j) & 1;
            if (x) merge(j, u, v);
        }
    }
    for (int u = 1; u <= n; u ++) {
        for (auto [v, w] : G[u]) {
            if (w % 2 == 0) {
                for (int k = 1; k <= 30; k ++) {
                    is[k][find(k, u)] = 1;
                    is[k][find(k, v)] = 1;
                }
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        int ans = 2;
        for (int i = 0; i <= 30; i ++) {
            if (find(i, u) == find(i, v)) {
                ans = 0;
                break;
            }
        }
        if (ans == 2) {
            for (int k = 1; k <= 30; k ++) {
                if (is[k][find(k, u)]) {
                    ans = 1;
                    break;
                }
            }
        }
        cout << ans << el;
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}

/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/