QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674529#7524. A Challenge For a Touristucup-team3161#WA 8ms48260kbC++173.3kb2024-10-25 16:17:412024-10-25 16:17:42

Judging History

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

  • [2024-10-25 16:17:42]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:48260kb
  • [2024-10-25 16:17:41]
  • 提交

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'