QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562196#7524. A Challenge For a Touristucup-team052#WA 0ms9988kbC++233.5kb2024-09-13 15:36:452024-09-13 15:36:46

Judging History

你现在查看的是最新测评结果

  • [2024-09-13 15:36:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9988kb
  • [2024-09-13 15:36:45]
  • 提交

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);
}
bool vis[N];
void dfs(int u,int ft){
	vis[u]=1;
	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;
		}
	}
	rep(u,1,n)if(!vis[u])dfs(u,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]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9936kb

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: 9932kb

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: 0ms
memory: 9988kb

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
6
-1
4
-1

result:

wrong answer 9th numbers differ - expected: '6', found: '4'