QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#155408 | #6695. Matching | ucup-team1001 | TL | 0ms | 0kb | C++23 | 1.6kb | 2023-09-01 16:37:04 | 2023-09-01 16:37:04 |
answer
#include<bits/stdc++.h>
#define ll long long
#define rep(i,l,r) for(int i = l; l <= r ? i <= r : i >= r;l <= r ? ++i : --i)
#define irep(i,l,r) for(int i = l; i <= r; ++i)
#define drep(i,r,l) for(int i = r; i >= l; --i)
#define yn(x) puts(x?"NO":"YES")
using namespace std;
const int N = 500999;
const int mod = 1000000007;
const int itinf = 1000000000;
const long long llinf = 100000000000000000;
inline ll read(){
ll s=0,w=1;
char chcc=getchar();
while(chcc<'0'||chcc>'9'){if(chcc=='-')w=-1;chcc=getchar();}
while(chcc>='0'&&chcc<='9') s=s*10+chcc-'0',chcc=getchar();
return s*w;
}
inline char rc(){
char readch = getchar();
while(!('0'<= readch && readch <= '9' || 'A' <= readch && readch <= 'Z' || 'a' <= readch && readch <= 'z'))readch = getchar();
return readch;
}
struct edge{
int u,v;ll c;
};
vector<edge>e;
int ql[N], qr[N];
int fa[N], ban[N],ans[N];
int find(int x){
if(fa[x] == x)return x;
fa[x] = find(fa[x]);
return fa[x];
}
void merge(int x,int y){
fa[find(x)] = find(y);
}
int main(){
ll n = read(), m = read(), q = read(), V = read()*2;
irep(i,1,n)fa[i] = i;
irep(i,1,m){
ll u = read(), v = read(), w = read();
e.push_back({u,v,w*2+1});
}
irep(i,1,q)ql[i] = read(), qr[i] = read();
for(ll b = 62; b >= 0; --b){
ll fl = V & (1ll << b);
if(fl)fl = 1;
if(fl == 0)irep(i,1,n)fa[i] = i;
irep(i,0,m-1){
if(ban[i])continue;
ll c = e[i].c, g = c & (1ll << b);
if(g)g = 1;
if((!fl) && g)merge(e[i].u,e[i].v);
if(fl && (!g))ban[i] = 1;
}
irep(i,1,q){
if(find(ql[i]) == find(qr[i]))ans[i] = 1;
}
}
irep(i,1,q)puts(ans[i] ? "Yes" : "No");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 9 3 -5 5 6 7 -1 9 1 2 3 -5 -4 -3 3 1 10 100