EEIC Programming Contest #0 : F. REIWA Path

最終問題、とはいえ割と典型感が強い。
https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/reiwa-path

問題

N頂点M辺の連結無向グラフが与えられる。
辺には整数値が振られている。
パスの長さとは、通った経路の辺の整数値のxorとし、点の間の距離は最短のパス長とする。

パス長が0となる頂点対は何組あるか。

解法

ある点を始点とし、各点までの距離を求めよう。
距離が一致する点同士は、パス長が0にできる。

辺を往復するとxorの値が0になる。
そこで、グラフのどこかに閉路がある場合、そこを1周まわることでそのxor分だけ全体の距離をいじることができる。
なので以下を求めよう。

• まずはDFS順に始点からの距離を求める。
• 途中閉路を検出した場合、その長さdを逐一覚えておく。

dをbitvectorとみなして複数の基底ベクトルを求めよう。
そうすると、最初に求めた視点から各点への距離に対し、各基底ベクトルを任意にxorすることができる。
なので、それによって各点の距離を最小化しよう。

vector<pair<int,ll>> E[1010];
ll D[1010];
vector<ll> V;

template<class C> int gf2_rank(vector<C>& V) { /* input */
	int i,j;
	int N=V.size();
	FOR(i,N) {
		int x=max_element(V.begin()+i,V.end())-V.begin();
		if(V[x]==0) break;
		swap(V[i],V[x]);
		C msb=1;
		while(msb<<1 <= V[i]) msb<<=1;
		FOR(j,N) if(j!=i) if(V[j]&msb) V[j]^=V[i];
	}
	return N-count(V.begin(),V.end(),0);
}

void dfs(int cur,ll v) {
	if(D[cur]>=0) {
		if(D[cur]!=v) V.push_back(D[cur]^v);
	}
	else {
		D[cur]=v;
		FORR(e,E[cur]) dfs(e.first,v^e.second);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		ll A;
		cin>>x>>y>>A;
		E[x-1].push_back({y-1,A});
		E[y-1].push_back({x-1,A});
	}
	MINUS(D);
	dfs(0,0);
	V.push_back(0);
	gf2_rank(V);
	V.erase(unique(ALL(V)),V.end());
	ll ret=0;
	map<ll,int> C;
	FOR(i,N) {
		FORR(v,V) D[i]=min(D[i],D[i]^v);
		ret+=C[D[i]];
		C[D[i]]++;
	}
	cout<<ret<<endl;
	
}

まとめ

全問自力で解けて良かった。