QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674265#7524. A Challenge For a Touristucup-team3161#WA 4ms32616kbC++172.3kb2024-10-25 14:48:072024-10-25 14:48:07

Judging History

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

  • [2024-10-25 14:48:07]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:32616kb
  • [2024-10-25 14:48:07]
  • 提交

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'