QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#155408#6695. Matchingucup-team1001TL 0ms0kbC++231.6kb2023-09-01 16:37:042023-09-01 16:37:04

Judging History

你现在查看的是最新测评结果

  • [2023-09-01 16:37:04]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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;
}

详细

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

output:


result: