QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562054 | #7524. A Challenge For a Tourist | ucup-team052# | WA | 1ms | 6144kb | C++23 | 2.1kb | 2024-09-13 14:38:55 | 2024-09-13 14:38:55 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=200005,K=20;
int n,m,Q;
int f[N][K],g[N][K];
vector<pair<int,int> >e[N];
struct dsu{
int fa[N];
dsu(){iota(fa,fa+N,0);}
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
void unite(int u,int v){fa[find(u)]=find(v);}
}o;
struct xxj{
int b[31];
void push(int x){
per(i,30,0)if(x>>i&1){
if(!b[i]){
b[i]=x;
return;
}
x^=b[i];
}
}
bool check(int x){
per(i,30,0)if(x>>i&1)x^=b[i];
return x==0;
}
}A[N];
int dep[N];
int val[N];
vector<tuple<int,int,int> >es;
void dfs(int u){
rep(i,1,K-1){
f[u][i]=f[f[u][i-1]][i-1];
g[u][i]=max(g[u][i-1],g[f[u][i-1]][i-1]);
}
for(auto&[v,w]:e[u])if(v!=f[u][0]){
dep[v]=dep[u]+1;
val[v]=val[u]^get<0>(es[w]);
f[v][0]=u;
g[v][0]=w;
dfs(v);
}
}
int query(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int dt=dep[u]-dep[v];
int ret=0;
per(i,K-1,0)if(dt>>i&1)ret=max(ret,g[u][i]),u=f[u][i];
if(u==v)return ret;
per(i,K-1,0)if(f[u][i]!=f[v][i])ret=max({ret,g[u][i],g[v][i]}),u=f[u][i],v=f[v][i];
return max({ret,g[u][0],g[v][0]});
}
signed main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
rep(i,1,m){
int u,v,w;
cin>>u>>v>>w;
es.eb(w,u,v);
}
sort(es.begin(),es.end());
vector<int>is(SZ(es));
rep(i,0,SZ(es)-1){
int w,u,v;
tie(w,u,v)=es[i];
if(o.find(u)!=o.find(v)){
is[i]=1;
o.unite(u,v);
e[u].eb(v,i),e[v].eb(u,i);
}else{
is[i]=0;
}
}
dfs(1);
rep(i,0,SZ(es)-1){
int w,u,v;
tie(w,u,v)=es[i];
if(i)A[i]=A[i-1];
if(!is[i]){
A[i].push(val[u]^val[v]^w);
}
}
cin>>Q;
while(Q--){
int u,v,x;
cin>>u>>v>>x;
int l=query(u,v),r=SZ(es)-1,ret=-1;
while(l<=r){
int mid=(l+r)>>1;
if(A[mid].check(val[u]^val[v]^x))ret=mid,r=mid-1;else l=mid+1;
}
if(ret==-1)printf("%d\n",-1);else printf("%d\n",get<0>(es[ret]));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6144kb
input:
6 6 5 6 3 6 2 2 1 2 1 2 3 2 2 4 3 4 5 4 3 1 3 1 1 3 3 1 3 5
output:
-1 2 4
result:
ok 3 number(s): "-1 2 4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 6068kb
input:
2 1 1 2 1 1 1 2 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5840kb
input:
5 10 1 2 4 2 2 0 1 1 7 2 1 7 4 1 1 5 5 1 4 1 4 5 2 6 1 1 2 2 4 7 10 1 4 3 1 2 5 3 2 1 3 5 5 2 4 0 3 2 0 2 1 2 2 3 6 5 1 7 2 3 3
output:
2 4 4 6 4 4 4 4 6 4
result:
wrong answer 2nd numbers differ - expected: '6', found: '4'