QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562180 | #7524. A Challenge For a Tourist | ucup-team052# | WA | 2ms | 10200kb | C++23 | 3.4kb | 2024-09-13 15:29:01 | 2024-09-13 15:29:01 |
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 qu[N],qv[N],qx[N];
vector<pair<int,int> >e[N];
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;
}
void mer(const XXJ&rhs){
per(i,30,0)if(rhs.b[i])push(rhs.b[i]);
}
};
struct node{
int type;
int x,y;
XXJ z;
};
struct dsu{
int fa[N],sz[N];
XXJ A[N];
dsu(){clear();}
void clear(){iota(fa,fa+N,0),fill(sz,sz+N,1);}
int find(int u){return u==fa[u]?u:find(fa[u]);}
void unite(int u,int v,int o,vector<node>&vec){
assert(fa[u]==u);
assert(fa[v]==v);
if(sz[u]<sz[v]){
fa[u]=v;
sz[v]+=sz[u];
if(o){
vec.pb((node){0,u,v});
vec.pb((node){1,u,0,A[u]});
vec.pb((node){1,v,0,A[v]});
A[v].mer(A[u]);
vec.pb((node){2,v,0,A[v]});
}
}else{
fa[v]=u;
sz[u]+=sz[v];
if(o){
vec.pb((node){0,v,u});
vec.pb((node){1,u,0,A[u]});
vec.pb((node){1,v,0,A[v]});
A[u].mer(A[v]);
vec.pb((node){2,u,0,A[u]});
}
}
}
}o;
void put(int u,int x,vector<node>&vec){
u=o.find(u);
vec.pb((node){1,u,0,o.A[u]});
o.A[u].push(x);
vec.pb((node){2,u,0,o.A[u]});
}
vector<tuple<int,int,int> >es;
vector<int>is;
vector<int>W;
int ans[N];
int T;
vector<node>vec[N];
void push(int t){
for(auto&x:vec[t]){
if(x.type==0){
o.fa[x.x]=x.y;
o.sz[x.y]+=o.sz[x.x];
}else if(x.type==2){
o.A[x.x]=x.z;
}
}
}
void pop(int t){
per(i,SZ(vec[t])-1,0){
auto&x=vec[t][i];
if(x.type==0){
o.fa[x.x]=x.x;
o.sz[x.y]-=o.sz[x.x];
}else if(x.type==1){
o.A[x.x]=x.z;
}
}
}
void go(int tim){
while(T<tim){
push(++T);
}
while(T>tim){
pop(T--);
}
}
int val[N];
bool check(int u,int v,int x){
int fu=o.find(u);
int fv=o.find(v);
if(fu!=fv)return 0;
return o.A[o.find(u)].check(val[u]^val[v]^x);
}
void solve(vector<int>&id,int l,int r){
if(id.empty())return;
if(l==r){
int ret=l<SZ(es)?get<0>(es[l]):-1;
for(auto&x:id){
ans[x]=ret;
}
return;
}
int mid=(l+r)>>1;
go(mid);
vector<int>L,R;
for(auto&x:id)if(check(qu[x],qv[x],qx[x]))L.pb(x);else R.pb(x);
id.clear(),id.shrink_to_fit();
solve(L,l,mid);
solve(R,mid+1,r);
}
void dfs(int u,int ft){
for(auto&[v,w]:e[u])if(v!=ft){
val[v]=val[u]^get<0>(es[w]);
dfs(v,u);
}
}
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());
is.assign(SZ(es),0);
rep(i,0,SZ(es)-1){
int w,u,v;
tie(w,u,v)=es[i];
int fu=o.find(u);
int fv=o.find(v);
if(fu!=fv){
is[i]=1;
o.unite(fu,fv,0,vec[i]);
e[u].eb(v,i);
e[v].eb(u,i);
}else{
is[i]=0;
}
}
dfs(1,0);
o.clear();
rep(i,0,SZ(es)-1){
int w,u,v;
tie(w,u,v)=es[i];
int fu=o.find(u);
int fv=o.find(v);
if(fu!=fv){
o.unite(fu,fv,1,vec[i]);
}else{
put(u,w^val[u]^val[v],vec[i]);
}
}
cin>>Q;
rep(i,1,Q){
cin>>qu[i]>>qv[i]>>qx[i];
}
vector<int>id(Q);
iota(id.begin(),id.end(),1);
solve(id,0,SZ(es));
rep(i,1,Q)printf("%d\n",ans[i]==SZ(es)?-1:ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9952kb
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: -100
Wrong Answer
time: 0ms
memory: 10200kb
input:
2 1 1 2 1 1 1 2 1
output:
-1
result:
wrong answer 1st numbers differ - expected: '1', found: '-1'