萌新求助
查看原帖
萌新求助
116015
bellmanford楼主2020/8/14 18:53

几乎要改的和题解一模一样了,样例过了,对拍也没有拍出问题←_←

然而还是错第二个点,请求帮助。

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int M=1e6+5;

int min(int x,int y){ return x<y?x:y; }
int max(int x,int y){ return x>y?x:y; }
void swap(int &x,int &y){ return (void)(x^=y^=x^=y); }

int n,m,q;
int read(){
	int x=0,y=1;char ch=getchar();
	while(ch<'0'||ch>'9') y=(ch=='-')?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*y;
}

int tot=0,num=0;
struct Edge{
	int x,y,z;
}e[M];
struct Query{
	int x,y;
}Q[M];

int p[M][35];
void insert(int x,int pos){
	for(int i=30;i>=0;i--){
		int c=(x>>i)&1;
		if(!c) continue ;
		if(p[pos][i]) x^=p[pos][i];
		else return (void)(p[pos][i]=x);
	}
}
int query(int x,int pos){
	for(int i=30;i>=0;i--){
		int c=(x>>i)&1;
//		if(!c||!p[pos][i]) continue ;
//		x^=p[pos][i];
		if((x^p[pos][i])<x) x^=p[pos][i];
	}
	return x;
}
void copy(int x,int y){ for(int i=30;i>=0;i--) p[y][i]=p[x][i]; }

int cnt=0,fa[M],de[M],dis[M];
struct BCJ{
	int x,y,dep;
}f[M];
int find(int x){ return fa[x]==x?fa[x]:find(fa[x]); }
int Xord(int x){ return fa[x]==x?dis[x]:dis[x]^Xord(fa[x]); }
void Merge(int x,int y,int z){
	if(de[x]<de[y]) swap(x,y);
	f[++cnt]=(BCJ){x,y,de[x]};
	fa[y]=x,dis[y]=z,de[x]=max(de[x],de[y]+1);
}
void Del(int id){
	int x=f[id].x,y=f[id].y,dep=f[id].dep;
	fa[y]=y,dis[y]=0,de[x]=dep;
}

vector<int> lazy[M<<2];
void Insert(int u,int l,int r,int L,int R,int id){
	if(L>r||R<l) return ;
	if(L<=l&&R>=r) return (void)(lazy[u].push_back(id));
	int mid=(l+r)>>1;
	Insert(u<<1,l,mid,L,R,id),Insert(u<<1|1,mid+1,r,L,R,id);
}
void Get_Ans(int u,int l,int r){
	int now=cnt,sz=lazy[u].size();
	for(int i=0;i<sz;i++){
		int id=lazy[u][i],x=e[id].x,y=e[id].y,z=e[id].z;
		z^=Xord(x)^Xord(y),x=find(x),y=find(y);
		if(x==y) insert(z,u);
		else Merge(x,y,z);
	}
	if(l==r){
		int x=Q[l].x,y=Q[l].y;
		if(find(x)!=find(y)) return (void)(printf("%lld\n",0));
		return (void)(printf("%lld\n",query(Xord(x)^Xord(y),u)));
	}
	int mid=(l+r)>>1;
	copy(u,u<<1),Get_Ans(u<<1,l,mid);
	copy(u,u<<1|1),Get_Ans(u<<1|1,mid+1,r);
	while(cnt>now) Del(cnt--);
}

int pre[M],suf[M];
map<pair<int,int>,int> Map;
void solve(){
	n=read(),m=read();tot=m;
	for(int i=1;i<=n;i++) fa[i]=i,de[i]=dis[i]=0;
	for(int i=1;i<=m;i++){
		e[i].x=read(),e[i].y=read(),e[i].z=read();
		if(e[i].x>e[i].y) swap(e[i].x,e[i].y);
		Map[make_pair(e[i].x,e[i].y)]=Map[make_pair(e[i].y,e[i].x)]=i;
		pre[i]=1,suf[i]=-1;
	}q=read();
	while(q--){
		int opt=read();
		if(opt==1){
			e[++tot].x=read(),e[tot].y=read(),e[tot].z=read();
			if(e[tot].x>e[tot].y) swap(e[tot].x,e[tot].y);
			Map[make_pair(e[tot].x,e[tot].y)]=Map[make_pair(e[tot].y,e[tot].x)]=tot;
			pre[tot]=num+1,suf[tot]=-1;
		}
		else if(opt==2){
			int x=read(),y=read();
			if(x>y) swap(x,y);
			suf[Map[make_pair(x,y)]]=num;
		}
		else if(opt==3) Q[++num].x=read(),Q[num].y=read();
	}
	for(int i=1;i<=tot;i++){
		if(suf[i]==-1) suf[i]=num;
		if(suf[i]>=pre[i]) Insert(1,1,num,pre[i],suf[i],i);
	}
	Get_Ans(1,1,num);
}

signed main(){
//	freopen("shuju.in","r",stdin);
//	freopen("std.out","w",stdout);
	solve();
}

或者给一组hack数据,感觉不尽。

顺便问问这个题的数据要怎么快速生成啊。

2020/8/14 18:53
加载中...