2049: [Sdoi2008]Cave 洞穴勘测 - #include <Seter> - using namespace Orz;

2049: [Sdoi2008]Cave 洞穴勘测

Seter posted @ 2011年9月12日 14:52 in BZOJ with tags DTP DisjointSet SDOI LCT , 3752 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=2049

RunID User Problem Result Memory Time Language Code Length Submit Time
150942 Seter 2049 Accepted 792 kb 596 ms C/Edit 723 B 2011-09-12 13:42:35

这题莫名其妙R1了……掉RP啊……

这题是维护一个动态森林……乍看是动态树其实真的是动态树……不过这题只要暴力就可以了!难道数据是随机的么?

其实这东西就是一个并查集……但是没有路径压缩(能否按秩合并?)……否则就很难destory了。

Cxy操作:x提根然后将x的父亲设为y。

Dxy操作:x提根,此时y的父亲必为x,所以将y的父亲清空即可。

Qxy操作:x提根,暴力查找y的根是不是x。

如何提根?很简单。把x到根的顺序颠倒过来就可以了。即原来a是b的父亲,让b成为a的父亲。

#include <stdio.h>
#include <string.h>
int n,m,f[10000];
inline getint(){
	int re=0,ch=getchar(),k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}inline void SetRoot(x){
	int y,t=f[x];
	for(f[x]=-1;(y=t)!=-1;x=y){t=f[y];f[y]=x;}
}main(){
	int ch,x;n=getint();
	memset(f,-1,sizeof(f));
	for(m=getint();m--&&(ch=getchar())>0;){
		SetRoot(x=getint()-1);
		if(ch=='C')f[x]=getint()-1;
		else if(ch=='D')f[getint()-1]=-1;
		else{
			for(ch=getint()-1;ch!=-1&&ch!=x;ch=f[ch]);
			puts(ch==x?"Yes":"No");
		}
	}return 0;
}

用LCT写了下,结果调了5个小时,今天睡觉的时候想到貌似少了个pushdown,结果真的少了个pushdown……

每个操作的执行方法挺多的,我的不是最优的……

首先让Access操作(简称A操作)返回最后一次接上去的时候的父亲,这样A(x)后A(y)返回的就是LCA了。

Q:A(x)后如果A(y)返回x,那么说明LCA是x,显然Yes;否则如果将xSplay到顶后有父亲,说明A(y)时被断掉了,也是Yes;否则No。

D:A(x)后A(y)返回的就是父亲,A(父亲)后splay儿子并将其根设为空

C:最麻烦的操作,为了将x旋到根,A(x)后splay(x),然后给x打上翻转标记……然后x就是根了(你可以想想为什么),将x的父亲设为y即可。

为了处理翻转标记,一定要弄清楚pushdown的顺序……一开始我在splay里pushdown,但是处理完x再处理fx的话,x可能又上了标记!所以5个小时犯二后我在rot操作里按照ffx,fx,x的顺序pushdown了,TLE->AC……

#include <stdio.h>
#define maxn 10000
typedef struct _Splay{struct _Splay *c[2],*f;_Bool r;}Splay,*PSplay;
Splay null,st[maxn];
inline PSplay fa(PSplay x){return x->f->c[0]==x||x->f->c[1]==x?x->f:&null;}
inline PSplay tran(PSplay x){PSplay t;if(x->r)x->r=0,(t=x->c[0])->r^=1,(x->c[0]=x->c[1])->r^=1,x->c[1]=t;return x;}
inline PSplay node(PSplay x){x->f=x->c[0]=x->c[1]=&null;return x;}
inline PSplay rot(PSplay x){
	PSplay fx=fa(x),ffx=tran(fa(fx));
	_Bool c=tran(fx)->c[1]==x,fc=ffx->c[1]==fx;tran(x);
	if(fx!=&null){
		x->f=fx->f;
		if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx;
		if(ffx!=&null)ffx->c[fc]=x;
		(fx->f=x)->c[!c]=fx;
	}return x;
}inline PSplay splay(PSplay x,PSplay p){
	PSplay fx,ffx;if(x==&null)return x;
	for(;(fx=fa(x))!=p;rot(x))if((ffx=fa(fx))!=p)rot((ffx->c[1]==fx)==(fx->c[1]==x)?fx:x);
	return tran(x);
}inline getint(){
	int re=0,ch=getchar();_Bool k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}inline PSplay Access(PSplay x){
	PSplay t=&null;
	while(splay(x,&null)->c[1]=t,(x=(t=x)->f)!=&null);
	return splay(t,&null);
}main(){
	int n,i=-1,x,y;
	null.f=null.c[0]=null.c[1]=&null;
	for(n=getint();++i!=n;node(st+i));
	for(n=getint();n--;){
		while((i=getchar())!='Q'&&i!='D'&&i!='C');
		if(i=='Q'){
			Access(st+(x=getint()-1));
			puts(Access(st+(y=getint()-1))!=st+x&&splay(st+x,&null)->f==&null?"No":"Yes");
		}else if(i=='D'){
			Access(st+(x=getint()-1));
			if(Access(st+(y=getint()-1))==st+x){
				Access(st+x);
				splay(st+y,&null)->f=&null;
			}else splay(st+x,&null)->f=&null;
		}else{
			Access(st+(x=getint()-1));
			splay(st+x,&null)->r^=1;
			st[x].f=splay(st+getint()-1,&null);
		}
	}return 0;
}
By Seter
xiaodao 说:
2011年9月22日 20:03

(目测你的方法不做 rev 标记的无根动态树。。)
@ 能否按秩合并?: 我查了原文,表示论文里专门提了一节讲这个优化,不过 Rank还原成子树的大小。
。我猜测这个优化也许对暴力合并能起到更好的效果。

Avatar_small
Seter 说:
2011年9月23日 12:15

我本来也是这么想的……不过这个不是一般的并茶几……比如提根时怎么维护rank?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee