Submission #1594099

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Edge {
	int from, to;
	ll cost;
	Edge() {}
	Edge(int f, int t, int 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) {
	while (val & (val - 1)) val = val & (val - 1);
	return 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 == 0) return;
	ll t = top(a);
	for (auto& v : w) if (t & v) v ^= a;
	w.push_back(a);
}

vector<ll> binary_basis(const vector<ll>& w) {
	vector<ll> res;
	for (auto v : w) {
		binary_basis_insert(res, v);
	}
	return res;
}

void dfs(int v, const 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;
	cin >> N >> M >> Q;
	Graph G(N);
	for (int i = 0; i < M; i++) {
		int f, t;
		ll p;
		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--) {
		int a, b;
		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