QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #490130 | #6679. Not Another Path Query Problem | yangqb | WA | 0ms | 1392kb | C++20 | 974b | 2024-07-25 11:38:25 | 2024-07-25 11:38:25 |
Judging History
answer
#include<cstdio>
using namespace std;
int n, m, q, fa[100005][65], b[65];
long long V;
int find(int x, int i) {
return x==fa[x][i] ? x : fa[x][i]=find(fa[x][i], i);
}
int main() {
scanf("%d%d%d%lld", &n, &m, &q, &V);
for(int i=1; i<=n; ++i)
for(int j=0; j<=61; ++j) fa[i][j] = i;
for(int j=60; ~j; --j)
if(V&(1ll<<j)) b[j] = 1;
for(int i=1; i<=m; ++i) {
int u, v;
long long w;
scanf("%d%d%lld", &u, &v, &w);
for(int j=60; ~j; --j) {
bool f = (w&(1ll<<j));
if((!b[j]) && f) fa[find(u, j)][j] = find(v, j);
else if(b[j] && (!f)) break;
}
if(w==V) fa[find(u, 61)][61]=find(v, 61);
}
for(int i=1; i<=q; ++i) {
int u, v, flag=0;
scanf("%d%d", &u, &v);
for(int j=61; ~j; --j)
if(find(u, j) == find(v, j)) {
flag = 1;
break;
}
puts(flag ? "Yes" : "No");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 1392kb
input:
9 8 4 5 1 2 8 1 3 7 2 4 1 3 4 14 2 5 9 4 5 7 5 6 6 3 7 15 1 6 2 7 7 6 1 8
output:
Yes No Yes No
result:
ok 4 token(s): yes count is 2, no count is 2
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 1360kb
input:
3 4 1 4 1 2 3 1 2 5 2 3 2 2 3 6 1 3
output:
No
result:
wrong answer expected YES, found NO [1st token]