QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#674265 | #7524. A Challenge For a Tourist | ucup-team3161# | WA | 4ms | 32616kb | C++17 | 2.3kb | 2024-10-25 14:48:07 | 2024-10-25 14:48:07 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,x,y) for (int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (int i=(x);i<(y);i++)
#define Dow(i,x,y) for (int i=(x);i>=(y);i--)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
inline ll read(){
ll x=0;
scanf("%lld",&x);
return x;
}
const int N = 2e5+10;
int n,m,q;
struct edge{
int x,y,z;
}e[N];
struct ask{
int x,y,z,id;
};
vector<ask>Q[N<<2];
struct xxj{
int v[30];
inline bool insert(int x){
Dow(i,29,0) if (x>>i&1){
if (!v[i]) return v[i]=x,1;
x^=v[i];
}
return 0;
}
inline bool Query(int x){
Dow(i,29,0) if (x>>i&1){
if (!v[i]) return 0;
x^=v[i];
}
return x==0;
}
}b;
int topb;
xxj stkb[50];
const int M = N*40;
int top,_pos[M],_fa[M],_f[M],_dep[M];
int fa[N],f[N],dep[N];
inline int Find(int x){
return fa[x]==x?x:Find(fa[x]);
}
inline int getf(int x){
return fa[x]==x?f[x]:getf(fa[x])^f[x];
}
inline void Push(int x){
++top,_pos[top]=x,_fa[top]=fa[x],_f[top]=f[x],_dep[top]=dep[x];
}
inline int Merge(int x,int y,int z){
int rtx=Find(x),rty=Find(y);
if (rtx==rty) return 0;
if (dep[rtx]>dep[rty]) swap(rtx,rty);
Push(rtx),Push(rty);
z^=getf(x)^getf(y);
fa[rtx]=rty,dep[rty]=max(dep[rty],dep[rtx]+1),f[rtx]=z;
return 1;
}
int ans[N];
inline void solve(int u,int l,int r){
if (l==r){
for (auto i:Q[u]) ans[i.id]=e[l].z;
return;
}
int mid=l+r>>1,tmptop=top;
stkb[++topb]=b;
For(i,l,mid){
if (Merge(e[i].x,e[i].y,e[i].z)) continue;
b.insert(getf(e[i].x)^getf(e[i].y)^e[i].z);
}
for (auto [x,y,z,id]:Q[u]){
int t=getf(x)^getf(y)^z;
if (b.Query(t)) Q[u<<1].pb((ask){x,y,z,id});
else Q[u<<1^1].pb((ask){x,y,z,id});
}
solve(u<<1^1,mid+1,r);
b=stkb[topb],--topb;
while (top>tmptop){
int u=_pos[top];
fa[u]=_fa[top];
dep[u]=_dep[top];
f[u]=_f[top];
--top;
}
solve(u<<1,l,mid);
}
int main(){
n=read(),m=read();
For(i,1,m) e[i]=(edge){read(),read(),read()};
sort(e+1,e+1+m,[](edge a,edge b){
return a.z<b.z;
});
q=read();
For(i,1,q){
int x=read(),y=read(),z=read();
Q[1].pb((ask){x,y,z,i});
}
// For(i,1,m) printf("edge %d %d %d\n",e[i].x,e[i].y,e[i].z);
For(i,1,n) fa[i]=i;
e[m+1].z=-1;
solve(1,1,m+1);
For(i,1,q) printf("%d\n",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 32616kb
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: 3ms
memory: 24300kb
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: 4ms
memory: 22736kb
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 1 4 1 0 4 4 4 4
result:
wrong answer 2nd numbers differ - expected: '6', found: '4'