记录编号 |
589130 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
不是一道路径查询问题 |
最终得分 |
100 |
用户昵称 |
健康铀 |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
1.401 s |
提交时间 |
2024-07-03 15:32:59 |
内存使用 |
11.75 MiB |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,cnt,nm[500010][3],vs[65],m,q,pre[100010],u,v,w,pd,top,sum,jl[500010][2],ns[500010];
inline long long read()
{
long long k=0,f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c&15);
return k*f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
long long find(long long x){
if(pre[x]==x)
return x;
return pre[x]=find(pre[x]);
}
void join(long long x,long long y){
long long fx=find(x),fy=find(y);
if(fx!=fy)
pre[fx]=fy;
}
void js(long long v1){
for(long long i=1;i<=n;i++)
pre[i]=i;
for(long long i=1;i<=m;i++)
if((nm[i][3]&v1)==v1)join(nm[i][1],nm[i][2]);
for(long long i=1;i<=q;i++)
if(find(jl[i][1])==find(jl[i][2]))ns[i]=1;
}
int main()
{
freopen("Paths.in","r",stdin);
freopen("Paths.out","w",stdout);
cin>>n>>m>>q>>v;
for(long long i=1;i<=m;i++){
long long x,y,z;
x=read(),y=read(),z=read();
nm[i][1]=x,nm[i][2]=y,nm[i][3]=z;
}
for(long long i=1;i<=q;i++)
jl[i][1]=read(),jl[i][2]=read();
for(long long i=0;i<=59;i++){
if(!((1ll<<i)&v)){
long long cnt=(((v>>i)+1)<<i);
js(cnt);
}
}
js(v);
for(long long i=1;i<=q;i++){
if(ns[i]==1){
printf("Yes\n");
}
else
printf("No\n");
}
return 0;
}