#C240129E. Not Another Path Query Problem

标签（Label）

• 二进制
• 分层图

网址（Website）

$\qquad$ Problem - J - Codeforces

题解（Solution）

$\qquad$转化为2进制后，从最高位开始枚举，当且仅当第 $k$ 位的数以及更高位的二进制位都大于等于 $V$ 的二进制位时，当前边的“与和”才会大于 $V$ ，因此用 $O(log_a)$ （ $a$ 是值域 ）来枚举 $k$ ，然后筛选出满足条件的边，将那些边两端的节点建立并查集，询问时 $O(log_a)$ 看两点有没有在同一个并查集内即可。

$\qquad$注意：相等时也是满足条件的，不要漏。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<bitset>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int N = 101234;
const int M = 501234;

int n,m,q,V;

struct Edge{int x,y,v;}e[M];

bitset<72> mul[M];
void get_mul(int p,int x){int k=1;while(x) mul[p][k]=x&1,x>>=1,k++;}


int fa[72][N];
inline int find(int p,int x){
	if(fa[p][x]==x) return x;
	else return fa[p][x]=find(p,fa[p][x]);
}

bitset<M> vst;
void Solve(){
	For(k,0,64) For(i,0,n) fa[k][i]=i;vst=~vst;
	Rof(k,64,1){
		if(mul[0][k]==1){//V
			for(int i=vst._Find_first();i<=m;i=vst._Find_next(i))
				if(mul[i][k]==0) vst[i]=false;
		}else{
			for(int i=vst._Find_first();i<=m;i=vst._Find_next(i)){
				if(mul[i][k]==1){
					int fx=find(k,e[i].x),fy=find(k,e[i].y);
					if(fx==fy) continue;
					fa[k][fx]=fy;
				}
			}
		}
	}for(int i=vst._Find_first();i<=m;i=vst._Find_next(i)){//相等的情况 
		int fx=find(0,e[i].x),fy=find(0,e[i].y);
		if(fx==fy) continue;
		fa[0][fx]=fy;
	}
}

void Count(int x=input(),int y=input()){
	For(k,0,64){
		int fx=find(k,x),fy=find(k,y);
		if(fx==fy) return cout<<"Yes\n",void();
	}return cout<<"No\n",void();
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q>>V;
	int Tim=clock();
	get_mul(0,V);
	For(i,1,m){
		int x=input(),y=input(),v=input();
		e[i]={x,y,v};get_mul(i,v);
	}Solve();
	while(q--) Count(); 
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}