QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#454015#877. Company At Dangergrass8cow#WA 16ms6844kbC++17916b2024-06-24 15:45:102024-06-24 15:45:10

Judging History

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

  • [2024-06-24 15:45:10]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:6844kb
  • [2024-06-24 15:45:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10;
int U[M],n,m,q,V[M],W[M],d[N];
bool vi[N];
#define pb push_back
vector<pair<int,int> >g[N];
void dfs(int x){
    vi[x]=1;
    for(auto it:g[x]){
        int v=it.first,w=it.second;
        if(vi[v])continue;
        d[v]=d[x]^w,dfs(v);
    }
}
int a[100];
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&U[i],&V[i],&W[i]);
        g[U[i]].pb({V[i],W[i]}),g[V[i]].pb({U[i],W[i]});
    }
    dfs(1);
    for(int i=0;i<m;i++){
        int z=d[U[i]]^d[V[i]]^W[i];if(!z)continue;
        for(int j=29;j>=0;j--)if((z>>j)&1){
            if(!a[j]){a[j]=z;break;}
            z^=a[j];
        }
    }
    for(int i=0,u,v;i<q;i++){
        scanf("%d%d",&u,&v);int z=d[u]^d[v];
        for(int j=29;j>=0;j--)z=min(z,z^a[j]);
        printf("%d\n",z);
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4156kb

input:

3 3 3
1 2 2
1 3 2
2 3 3
1 2
1 3
2 3

output:

1
1
0

result:

ok 3 number(s): "1 1 0"

Test #2:

score: 0
Accepted
time: 0ms
memory: 4076kb

input:

7 10 5
1 2 45
2 3 11
2 4 46
3 4 28
3 5 59
3 6 12
3 7 3
4 5 11
5 6 23
6 7 20
1 4
2 6
3 5
1 7
5 5

output:

1
5
0
5
0

result:

ok 5 number(s): "1 5 0 5 0"

Test #3:

score: -100
Wrong Answer
time: 16ms
memory: 6844kb

input:

10000 60059 25000
5140 602 0
5140 4077 546574455686537395
4077 602 546574455686537394
5140 5492 401628381435124761
5492 602 401628381435124763
5140 4907 231352666654267087
4907 602 231352666654267083
5140 9430 281314177097774626
9430 602 281314177097774634
5140 6477 63541404444272256
6477 602 635414...

output:

-1073741824
-1073741824
1073741824
-2147483648
1073741824
-2147483648
-1073741824
-1073741824
1073741824
-1073741824
0
0
1073741824
-1073741824
-2147483648
0
0
0
1073741824
0
-2147483648
-1073741824
-1073741824
0
1073741824
1073741824
0
0
0
-1073741824
0
0
1073741824
0
1073741824
-1073741824
-107374...

result:

wrong answer 1st numbers differ - expected: '0', found: '-1073741824'