Submission #1594132

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
struct Edge {
	int from, to;
	ll cost;
	Edge(int f, int t, ll c) : from(f), to(t), cost(c) {}
};
 
using Edges = vector<Edge>;
using Graph = vector<Edges>;
 
vector<ll> cycles;
 
int used[100000];
ll d[100000];
 
ll top(ll val) { return 1ll << (63ll - __builtin_clzll(val)); }
 
void binary_basis_insert(vector<ll>& w, ll a) {
	for (auto v : w) {
		ll t = top(v);
		if (t & a) a ^= v;
	}
	if (!a) return;
	ll t = top(a);
	for (auto& v : w) if (t & v) v ^= a;
	w.push_back(a);
}
 
vector<ll> binary_basis(vector<ll>& w) {
	vector<ll> res;
	for (auto v : w) binary_basis_insert(res, v);
	return res;
}
 
void dfs(int v, Graph& G) {
	used[v] = 1;
	for (auto e : G[v]) {
		if (used[e.to]) cycles.push_back(d[v] ^ d[e.to] ^ e.cost);
		else d[e.to] = d[v] ^ e.cost, dfs(e.to, G);
	}
}
 
int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, Q, f, t, a, b;
	ll p;
	cin >> N >> M >> Q;
	Graph G(N);
	for (int i = 0; i < M; i++) {
		cin >> f >> t >> p;
		G[f].emplace_back(f, t, p);
		G[t].emplace_back(t, f, p);
	}
	dfs(0, G);
	auto bit = binary_basis(cycles);
	sort(bit.rbegin(), bit.rend());
	while (Q--) {
		cin >> a >> b;
		ll res = d[a] ^ d[b];
		for (auto v : bit) {
			ll t = top(v);
			if (!(res & t)) {
				res ^= v;
			}
		}
		printf("%lld\n", res);
	}
	return 0;
}

Submission Info

Judge Result