AOJ 2416: XOR Cloister

たまにはAOJ-ICPCではないAOJを解くことで良問が残っていることを思い出す。

ループがあると、そこを1周することで場所を変えずにxor値だけを変えることができるので、これらのループのxorを全部列挙して基底を求めればよいが、
これはxorの性質上、dfs木を作って累積xorを求めていくことで容易に達成できる。(LCAから根まで2回とおることでxorが消えることが大事)

#include<stdio.h>
#include<algorithm>
#include<vector>
#define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
 
#define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

using namespace std;
vector<pair<int,long long> >g[210000];
long long val[410000];
long long kt[410000];
int v[410000];
int sz;
void dfs(int a,int b){
	v[a]=1;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i].first==b)continue;
		if(!v[g[a][i].first]){
			val[g[a][i].first]=(val[a]^g[a][i].second);
			dfs(g[a][i].first,a);
		}else{
			kt[sz++]=(val[a]^val[g[a][i].first]^g[a][i].second);
		}
	}
}
int main(){
	BEGIN_STACK_EXTEND(120*1024*1024);
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<b;i++){
		int p,q;
		long long r;
		scanf("%d%d%lld",&p,&q,&r);
		g[p].push_back(make_pair(q,r));
		g[q].push_back(make_pair(p,r));
	}
	sz=0;
	dfs(0,-1);
	int now=0;
	for(int i=59;i>=0;i--){
		int at=-1;
		for(int j=now;j<sz;j++){
			if(kt[j]&(1LL<<i)){
				at=j;break;
			}
		}
		if(!~at)continue;
		if(at!=now)swap(kt[at],kt[now]);
		for(int j=0;j<sz;j++){
			if(now==j)continue;
			if(kt[j]&(1LL<<i))kt[j]^=kt[now];
		}
		now++;
	}
	//for(int i=0;i<a;i++)printf("%lld\n",val[i]);
	//for(int i=0;i<now;i++)printf("%lld\n",kt[i]);
	for(int i=0;i<c;i++){
		int p,q;scanf("%d%d",&p,&q);
		long long ret=(val[p]^val[q]);
		for(int j=0;j<now;j++){
			if(ret<(ret^kt[j]))ret^=kt[j];
		}
		printf("%lld\n",ret);
	}
	END_STACK_EXTEND;
}