记录编号	157797	评测结果	AAAAAAAAAA
题目名称	[SDOI 2008]Cave 洞穴勘测	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	1.986 s
提交时间	2015-04-10 11:46:28	内存使用	3.31 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============

///==============var declaration=================
const int MAXN=10010;
int n,m;
int fa[MAXN],lc[MAXN],rc[MAXN],path[MAXN];
bool rev[MAXN];
///==============function declaration============
void Access(int x);void Link(int x,int y);void Cut(int x,int y);int Findroot(int x);
void Splay(int x);void Lrotate(int x);void Rrotate(int x);void push_down(int x);
///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
   freopen("sdoi2008_cave.in","r",stdin);
   freopen("sdoi2008_cave.out","w",stdout);
	//endif
	scanf("%d%d",&n,&m);
	memset(lc,-1,sizeof(lc));memset(rc,0,sizeof(rc));
	memset(fa,-1,sizeof(fa));memset(rev,false,sizeof(rev));
	while (m--){
		char cmd[10];scanf("%s",cmd);
		if (cmd[0]=='C'){///Connect
			int x,y;scanf("%d%d",&x,&y);
			Link(x,y);
		}
		else if (cmd[0]=='D'){///Destroy
			int x,y;scanf("%d%d",&x,&y);
			Cut(x,y);
		}
		else if (cmd[0]=='Q'){
			int x,y;scanf("%d%d",&x,&y);
			if (Findroot(x)==Findroot(y))
				printf("Yes\n");
			else
				printf("No\n");
		}
		else printf("Init Err!\n");
	}
}
///================fuction code====================
void Access(int x){
	int v=x,u=-1;
	while (v!=-1){
		Splay(v);
		rc[v]=u;
		if (u!=-1)
			fa[u]=v;
		u=v;v=fa[v];
	}
}
void Link(int x,int y){
	Access(x);Splay(x);
	rev[x]^=1;push_down(x);
	fa[x]=y;
	Access(x);
}
void Cut(int x,int y){
	Access(x);Splay(x);
	rev[x]^=1;push_down(x);
	Access(y);Splay(y);push_down(y);
	if (lc[y]==x)
		lc[y]=-1;
	else if (rc[y]==x)
		rc[y]=-1;
	fa[x]=-1;
}
void Splay(int x){
	int tot=0;int temp=x;
	while (rc[fa[temp]]==temp||lc[fa[temp]]==temp){
		path[++tot]=temp;
		temp=fa[temp];
	}
	path[++tot]=temp;
	for(int i=tot;i>=1;i--)
		push_down(path[i]);
	while (fa[x]!=-1){
		int dir1,dir2;
		if (lc[fa[x]]==x) dir1=0;
		else if (rc[fa[x]]==x) dir1=1;
		else dir1=-1;
		if (dir1==-1) break;
		int p=fa[x];
		if (lc[fa[p]]==p) dir2=0;
		else if (rc[fa[p]]==p) dir2=1;
		else dir2=-1;
		if (dir2==-1){
			if (dir1==0)
				Lrotate(fa[x]);
			else
				Rrotate(fa[x]);
		}
		else if (dir1==dir2){
			if (dir1==0){
				Lrotate(fa[p]);
				Lrotate(fa[x]);
			}
			else{
				Rrotate(fa[p]);
				Rrotate(fa[x]);
			}
		}
		else if (dir1==0)
			Lrotate(fa[x]);
		else if (dir1==1)
			Rrotate(fa[x]);
	}
}
void push_down(int x){
	if (rev[x]){
		rev[x]=false;
		if (lc[x]!=-1)
			rev[lc[x]]^=1;
		if (rc[x]!=-1)
			rev[rc[x]]^=1;
		swap(lc[x],rc[x]);
	}
}
void Lrotate(int x){
	int y=lc[x];
	fa[y]=fa[x];
	if (fa[x]!=-1){
		if (lc[fa[x]]==x)
			lc[fa[x]]=y;
		else if (rc[fa[x]]==x)
			rc[fa[x]]=y;
	}
	lc[x]=rc[y];
	if (rc[y]!=-1)
		fa[rc[y]]=x;
	rc[y]=x;fa[x]=y;
}
void Rrotate(int x){
	int y=rc[x];
	fa[y]=fa[x];
	if (fa[x]!=-1){
		if (lc[fa[x]]==x)
			lc[fa[x]]=y;
		else if (rc[fa[x]]==x)
			rc[fa[x]]=y;
	}
	rc[x]=lc[y];
	if (lc[y]!=-1)
		fa[lc[y]]=x;
	lc[y]=x;fa[x]=y;
}
int Findroot(int x){
	Access(x);Splay(x);
	while (lc[x]!=-1)
		x=lc[x];
	return x;
}