QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#674529 | #7524. A Challenge For a Tourist | ucup-team3161# | WA | 8ms | 48260kb | C++17 | 3.3kb | 2024-10-25 16:17:41 | 2024-10-25 16:17:42 |
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
#define siz(x) ((int)x.size())
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 = 4e5+10;
int n,m,q;
struct edge{
int x,y,z;
}e[N];
vector<pa>E[N];
inline void Add(int x,int y,int z){
E[x].pb(mp(y,z));
E[y].pb(mp(x,z));
//printf("tree %d %d %d\n",x,y,z);
}
int dd[N];
inline void Dfs(int u,int fa){
for (auto [v,w]:E[u]) if (v!=fa){
dd[v]=dd[u]^w;
Dfs(v,u);
}
}
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;
}
}emp;
vector<int>v[N];
vector<xxj>b[N];
inline xxj Merge(xxj a,xxj b){
xxj ret=a;
Dow(i,29,0) if (b.v[i]) a.insert(b.v[i]);
return ret;
}
int fa[N];
inline int Find(int x){
return fa[x]==x?x:fa[x]=Find(fa[x]);
}
inline int Merge(int x,int y){
x=Find(x),y=Find(y);
if (x==y) return 0;
fa[x]=y;
return 1;
}
int dep[N],anc[N][22],w[N];
bool vis[N];
vector<int>ee[N];
inline void dfs(int u){
vis[u]=1;
dep[u]=dep[anc[u][0]]+1;
For(i,1,20) anc[u][i]=anc[anc[u][i-1]][i-1];
for (auto v:ee[u]){
anc[v][0]=u;
dfs(v);
}
}
inline int LCA(int x,int y){
if (dep[x]>dep[y]) swap(x,y);
if (dep[y]>dep[x]) Dow(i,20,0) if (dep[anc[y][i]]>=dep[x]) y=anc[y][i];
if (x==y) return x;
Dow(i,20,0) if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
inline int Query2(int x,int y){
int l=0,r=siz(v[x])-1,ret=r;
while (l<=r){
int mid=l+r>>1;
if (b[x][mid].Query(y)) ret=mid,r=mid-1;
else l=mid+1;
}
return v[x][ret];
}
inline int Query(int x,int y){
Dow(i,20,0){
int t=anc[x][i];
if (!t) continue;
if (!b[t].back().Query(y)) x=anc[x][i];
}
if (b[x].back().Query(y)) return Query2(x,y);
x=anc[x][0];
if (x==0) return -1;
if (!b[x].back().Query(y)) return -1;
return Query2(x,y);
}
int main(){
//freopen("a.out","w",stdout);
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;
});
For(i,1,n) fa[i]=i;
For(i,1,m) if (Merge(e[i].x,e[i].y)) Add(e[i].x,e[i].y,e[i].z);
Dfs(1,0);
For(i,1,n*2) fa[i]=i;
For(i,1,n) b[i].pb(emp);
int cnt=n;
For(i,1,m){
int x=Find(e[i].x),y=Find(e[i].y);
if (x==y){
int t=dd[e[i].x]^dd[e[i].y]^e[i].z;
// printf("add %d %d %d %d %d\n",e[i].x,e[i].y,e[i].z,t,x);
// b[x].insert(t);
auto tmp=b[x].back();
tmp.insert(t);
b[x].pb(tmp);
v[x].pb(e[i].z);
} else {
++cnt;
// b[cnt]=Merge(b[x],b[y]);
b[cnt].pb(Merge(b[x].back(),b[y].back()));
v[cnt].pb(e[i].z);
fa[x]=cnt,fa[y]=cnt;
w[cnt]=e[i].z;
ee[cnt].pb(x);
ee[cnt].pb(y);
}
}
Dow(i,cnt,1) if (!vis[i]) dfs(i);
q=read();
while (q--){
int x=read(),y=read(),z=read();
if (Find(x)!=Find(y)){
puts("-1");
continue;
}
int l=LCA(x,y);
printf("%d\n",Query(l,dd[x]^dd[y]^z));
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 47664kb
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: 8ms
memory: 48260kb
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: 3ms
memory: 46684kb
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 6 -1 -1 4 -1 7 -1 7 -1
result:
wrong answer 7th numbers differ - expected: '6', found: '7'