QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#454015 | #877. Company At Danger | grass8cow# | WA | 16ms | 6844kb | C++17 | 916b | 2024-06-24 15:45:10 | 2024-06-24 15:45:10 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'