Codeforces #507 Div1 C. Network Safety

本番誤ってCを飛ばしDに挑むという愚行をやらかした。
http://codeforces.com/contest/1039/problem/C

問題

N頂点M辺のシンプルがグラフが与えられる。
各頂点には整数C[i]が設定されている。C[i]は2^k未満の非負整数である。
また、辺の両端の頂点u,vではC[u]!=C[v]である。

ある整数0≦x＜2^kに対し、頂点の一部にC[i]にxor xを適用した場合、辺の両端のC[u]!=C[v]を維持できるようなxおよび適用先の頂点の部分集合の組み合わせを求めよ。

解法

xおよび部分集合の取り方(2^k)*(2^N)通りのうち、条件を満たさないものを考える。
ある辺(u,v)に対し、x=C[u]^C[v]となるxを適用する場合、u,vの片方だけに適用してしまうと条件を満たさないことになる。

そこで、まず全辺をx=C[u]^C[v]で分類し、xが等しい辺同士をまとめて扱おう。
そのような辺について、連結成分内の全頂点は全体をxor xするか全体をxor xしないかのいずれかである。
よってこのxについて部分集合の選び方は2^(連結成分数)だけになる。

以下のコードではunion findを高速に何度も実行するため巻き戻し可能なUFを使っている。

int N,M,K;
map<ll,vector<pair<int,int>>> E;
ll C[505050];
ll p2[505050];
ll mo=1000000007;
ll ret=0;

template<int um> class UF_pop {
	public:
	vector<int> par,rank; vector<vector<int>> hist;
	UF_pop() {par=rank=vector<int>(um,0); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):operator[](par[x]);}
	void pop() {
		if(hist.size()) {
			auto a=hist.back();
			hist.pop_back();
			par[a[0]]=a[1]; rank[a[0]]=a[2];
			par[a[3]]=a[4]; rank[a[3]]=a[5];
		}
	}
	void operator()(int x,int y) {
		x=operator[](x); y=operator[](y);
		hist.push_back({x,par[x],rank[x],y,par[y],rank[y]});
		if(x==y) return;
		if(rank[x]<rank[y]) par[x]=y;
		else rank[x]+=(rank[x]==rank[y]), par[y]=x;
	}
};
UF_pop<505050> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,501000) p2[i+1]=p2[i]*2%mo;
	
	
	cin>>N>>M>>K;
	FOR(i,N) cin>>C[i];
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[C[x]^C[y]].push_back({x,y});
	}
	
	ll ret=p2[N]*p2[K]%mo;
	FORR(e,E) {
		int num=0;
		ret-=p2[N];
		FORR(v,e.second) {
			if(uf[v.first]!=uf[v.second]) {
				num++;
				uf(v.first,v.second);
			}
		}
		FOR(i,num) uf.pop();
		ret+=p2[N-num];
	}
	cout<<((ret%mo+mo)%mo)<<endl;
	
}

まとめ

これは普通に自力で解けていた…。