Submission #1594148

---

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> cy;
int used[100000];
ll d[100000];
ll top(ll val){return 1ll<<(63ll - __builtin_clzll(val));}
void biin(vector<ll>&w,ll a){
	for(ll&v:w)if(top(v)&a)a^=v;
	if(!a)return;
	ll t=top(a);
	for(ll&v:w)if(t&v)v^=a;
	w.push_back(a);
}
vector<ll> bi(vector<ll>&w){
	vector<ll>res;
	for(ll&v:w)biin(res,v);
	sort(res.rbegin(),res.rend());
	return res;
}
void dfs(int v,Graph&G){
	used[v]=1;
	for(auto&e:G[v]){
		if(used[e.to])cy.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);
	while(M--){
		cin>>f>>t>>p;
		G[f].emplace_back(f,t,p);
		G[t].emplace_back(t,f,p);
	}
	dfs(0,G);
	auto bit=bi(cy);
	while(Q--){
		cin>>a>>b;
		ll res=d[a]^d[b];
		for(ll&v:bit)if(!(res&top(v)))res^=v;
		printf("%lld\n",res);
	}
	return 0;
}

Submission Info

Judge Result