[bzoj] 2049: [Sdoi2008]Cave 洞穴勘测

发表于   |   分类于   |  

热烈庆祝我的blog可以显示多行注释了QAQ

题意

给定森林,删边添边,查询连通性

分析

用一个不常用的GetRoot即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/****************************************\
* Author : ztx
* Title  : [bzoj] 2049: [Sdoi2008]Cave 洞穴勘测
* ALG    : LCT复习
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
typedef long long ll ;

inline int GETCHAR() {
truestatic const int LEN = 1<<15 ;
truestatic char BUF[LEN] , *S = BUF , *T = BUF ;
trueif (S == T) {
truetrueT = (S=BUF)+fread(BUF , 1 , LEN , stdin) ;
truetrueif (S == T) return EOF ;
true}
truereturn *S ++ ;
}

int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=GETCHAR() , CH<'!') ;
    if (CH == '-') NEG = true , CH = GETCHAR() ;
    while (ret = ret*10+CH-'0' , CH=GETCHAR() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void reads(TP& ret) {
truewhile (ret=GETCHAR() , ret<'!') ;
truewhile (CH=GETCHAR() , CH>'!') ;
}

#define  maxn  10010LL

int fa[maxn] = {0} , ch[maxn][2] = {0} ;
bool rev[maxn] = {0} ;

#define  null     0LL
#define  left(u)  ch[u][0]
#define  right(u) ch[u][1]

inline void Exchange(int&a,int&b) {int c=a;a=b;b=c;}
inline bool Isrt(int u) { return !fa[u] || (left(fa[u])!=u&&right(fa[u])!=u) ; }
inline void Clear(int u) {
trueif (!u) return ;
trueif (rev[u]) {
truetruerev[u] = false ;
truetrueExchange(left(u),right(u)) ;
truetruerev[left(u)] ^= true ;
truetruerev[right(u)] ^= true ;
true}
}

inline void Rot(int x,bool d) {
trueint y = fa[x] , z = fa[y] ;
trueif (left(z) == y) left(z) = x ;
trueelse if (right(z) == y) right(z) = x ;
truefa[x] = z , fa[ch[x][d]] = y , ch[y][!d] = ch[x][d] ;
truech[x][d] = y , fa[y] = x ;
//	Maintain(y);
}
inline void Splay(int x){
trueint y , z ;
trueClear(x) ;
truewhile (!Isrt(x)) {
truetruey = fa[x] , z = fa[y] ;
truetrueClear(z) , Clear(y) , Clear(x) ;
truetrueif (Isrt(y)) Rot(x,ch[y][0]==x) ;
truetrueelse if(ch[z][0] == y) {
truetruetrueif (ch[y][0] == x) Rot(y,1) ;
truetruetrueelse Rot(x,0) ; Rot(x,1) ;
truetrue} else {
truetruetrueif(ch[y][1] == x) Rot(y,0) ;
truetruetrueelse Rot(x,1) ; Rot(x,0) ;
truetrue}
true}
true//Maintain(x) ;
}

inline void Access(int u) {
truefor (int v=null ; u ; right(u)=v,v=u,u=fa[u]) Splay(u) ;
}

inline void MakeRoot(int u) {
trueAccess(u) , Splay(u) , rev[u] ^= true ;
}

inline void Link(int u , int v) {
trueMakeRoot(u) , fa[u] = v ;
}

inline void Cut(int u , int v) {
trueMakeRoot(u) , Access(v) , Splay(v) , fa[u]=left(v)=null ;
}

inline int GetRoot(int u) {
truefor (Access(u),Splay(u) ; Clear(u),left(u) ; u=left(u)) ; return u ;
}

inline void Query(int u , int v) {
trueputs(GetRoot(u)==GetRoot(v) ? "Yes" : "No") ;
}

int n , m , cmd , u , v ;

int main() {
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(n) , read(m) ;
truewhile (m --> 0) {
truetruereads(cmd) , read(u) , read(v) ;
truetrueif (cmd == 'C') Link(u,v) ;
truetrueif (cmd == 'D') Cut(u,v) ;
truetrueif (cmd == 'Q') Query(u,v) ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章