求助90分,最后一个点WA了
查看原帖
求助90分,最后一个点WA了
103109
传奇666666楼主2020/8/18 20:52
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+10,M=1e5+10;
struct edge
{
	int u,v,w;
}e[M];
int n,m,q,aa[M][3],bcj[N],bo[N][N];
int v[N+M],mxx[N+M],son[N+M][2],fa[N+M],rev[N+M];
int st[N+M],top,ans[M];
bool book[N][N];
bool cmp(edge x,edge y){return x.w<y.w;}
void pushup(int x)
{
	mxx[x]=max(v[x],max(mxx[son[x][0]],mxx[son[x][1]]));
	return;
}
void pushdown(int x)
{
	if(!rev[x]) return;
	if(son[x][0]) swap(son[son[x][0]][0],son[son[x][0]][1]),rev[son[x][0]]^=1;
	if(son[x][1]) swap(son[son[x][1]][0],son[son[x][1]][1]),rev[son[x][1]]^=1;
	rev[x]=0;
	return;
}
void rotate(int x)
{
	int a=fa[x],b=fa[a];
	int wz1=(son[a][1]==x),son1=son[x][wz1^1];
	if(son[b][0]==a||son[b][1]==a) son[b][son[b][1]==a]=x;
	son[a][wz1]=son1,son[x][wz1^1]=a;
	if(son1) fa[son1]=a;
	fa[a]=x;fa[x]=b;
	pushup(a);
	pushup(x);
	return;
}
void splay(int x)
{
	int now=x;st[++top]=now;
	while(son[fa[now]][0]==now||son[fa[now]][1]==now) now=fa[now],st[++top]=now;
	while(top) pushdown(st[top]),top--;
	while(son[fa[x]][0]==x||son[fa[x]][1]==x)
	{
		int a=fa[x],b=fa[a];
		if(son[b][0]==a||son[b][1]==a)
			if(son[son[b][0]][0]==x||son[son[b][1]][1]==x) rotate(a);
			else rotate(x);
		rotate(x);
	}
	pushup(x);
	return;
}
void access(int x)
{
	int tmp=0;
	while(x)
	{
		splay(x);
		son[x][1]=tmp;
		pushup(x);
		tmp=x;x=fa[x];
	}
	return;
}
void makert(int x)
{
	access(x);
	splay(x);
	swap(son[x][0],son[x][1]);
	rev[x]^=1;
	return;
}
void split(int x,int y)
{
	makert(x);
	access(y);
	splay(y);
	return;
}
void link(int x,int y)
{
//	printf("link:%d %d\n",x,y);
	makert(x);
	fa[x]=y;
	return;
}
void cut(int x,int y)
{
//	printf("cut:%d %d\n",x,y);
	split(x,y);
	fa[x]=son[y][0]=0;
	pushup(x);
	return;
}
void del(int x,int val)
{
	int u=x;
	while(1)
	{
		if(v[u]==val) break;
		else if(mxx[son[u][0]]==val) u=son[u][0];
		else u=son[u][1];
	}
	splay(u);
	int x1=son[u][0],x2=son[u][1];
	while(son[x1][1]) x1=son[x1][1];
	while(son[x2][0]) x2=son[x2][0];
	cut(u,x1);
	cut(u,x2);
	return;
}
int find(int x){return bcj[x]==x?x:bcj[x]=find(bcj[x]);}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;i++) v[i]=0,mxx[i]=0;
	for(int i=1;i<=m;i++) v[n+i]=e[i].w,mxx[n+i]=e[i].w;
	for(int i=1;i<=m;i++)
		bo[e[i].u][e[i].v]=bo[e[i].v][e[i].u]=n+i;
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d",&aa[i][0],&aa[i][1],&aa[i][2]);
		if(aa[i][0]==2) book[aa[i][1]][aa[i][2]]=book[aa[i][2]][aa[i][1]]=1;
	}
	for(int i=1;i<=n;i++) bcj[i]=i;
	for(int i=1;i<=m;i++)
	{
		if(book[e[i].u][e[i].v]) continue;
		int x=find(e[i].u),y=find(e[i].v);
		if(x==y) continue;
		bcj[x]=y;
		link(e[i].u,bo[e[i].u][e[i].v]);
		link(e[i].v,bo[e[i].u][e[i].v]);
	}
	for(int i=q;i>=1;i--)
	{
		if(aa[i][0]==1)
		{
			split(aa[i][1],aa[i][2]);
			ans[i]=mxx[aa[i][2]];
		}
		else
		{
			split(aa[i][1],aa[i][2]);
			if(mxx[aa[i][2]]<=v[bo[aa[i][1]][aa[i][2]]]) continue;
			del(aa[i][2],mxx[aa[i][2]]);
			link(aa[i][1],bo[aa[i][1]][aa[i][2]]);
			link(aa[i][2],bo[aa[i][1]][aa[i][2]]);
		}
	}
	for(int i=1;i<=q;i++)
		if(aa[i][0]==1) printf("%d\n",ans[i]);
	return 0;
}
2020/8/18 20:52
加载中...