「BZOJ-2049」 [Sdoi2008]Cave 洞穴勘测-Link-Cut Tree

辉辉热衷于洞穴勘测。某天,他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测,辉辉发现这片区域由n个洞穴(分别编号为1到n)以及若干通道组成,并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来,那么这两个洞穴就是连通的,按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏,然而通道不太稳定,时常因为外界影响而发生改变,比如,根据有关仪器的监测结果,123号洞穴和127号洞穴之间有时会出现一条通道,有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示:如果监测到洞穴u和洞穴v之间出现了一条通道,终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁,终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算,辉辉发现一个奇怪的现象:无论通道怎么改变,任意时刻任意两个洞穴之间至多只有一条路径。因而,辉辉坚信这是由于某种本质规律的支配导致的。因而,辉辉更加夜以继日地坚守在终端机之前,试图通过通道的改变情况来研究这条本质规律。然而,终于有一天,辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸(终端机也足够坚固无法破坏),转而求助于你,说道:“你老兄把这程序写写吧”。辉辉希望能随时通过终端机发出指令 Query u v,向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前,JSZX洞穴群中没有任何通道存在。

题解

时隔两个月,补一下2017-01-21的坑。

LCT 模板题,直接用 findRoot 操作判断就好了…

$540ms$,说明我的 LCT 常数不错,然而前面 900B 的看上去是并查集+玄学暴力。

代码

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/*
* created by xehoth on 21-01-2017
* updated by xehoth on 21-03-2017
*/
#include <bits/stdc++.h>
const int MAXN = 10010;
struct Node *null;
struct Node {
Node *c[2], *fa;
bool rev;
Node *top;
inline void maintain() {
}
inline void reverse() {
rev ^= 1, std::swap(c[0], c[1]);
}
inline void pushDown() {
rev ? c[0]->reverse(), c[1]->reverse(), rev = false : 0;
}
inline bool relation() {
return this == fa->c[1];
}
inline bool check() {
return this == fa->c[relation()];
}
inline void preview() {
if (check()) fa->preview();
pushDown();
}
inline void rotate(bool f) {
Node *o = fa;
top = o->top;
o->pushDown(), pushDown();
(fa = o->fa)->c[o->relation()] = this;
(o->c[f] = c[!f])->fa = o;
(c[!f] = o)->fa = this;
o->maintain();
}
inline void splay() {
Node *o = fa;
bool f;
for (pushDown(); o != null; o = fa) {
if (o->fa == null) {
rotate(o->c[1] == this);
} else {
(f = o->c[1] == this) == (o->fa->c[1] == o)
? (o->rotate(f), rotate(f)) : (rotate(f), rotate(!f));
}
}
maintain();
}
inline void expose(Node *p = null) {
splay();
if (c[1] != null)
c[1]->top = this, c[1]->fa = null;
(c[1] = p)->fa = this;
maintain();
}
inline Node *access() {
Node *x = this;
for (x->expose(); x->top; x = x->top)
x->top->expose(x);
return x;
}
inline void makeRoot() {
access(), splay(), reverse();
}
inline void link(Node *f) {
Node *x = access();
x->reverse(), x->top = f;
}
inline void cut(Node *y) {
Node *x = this;
x->expose(), y->expose();
if (x->top == y) x->top = NULL;
if (y->top == x) y->top = NULL;
}
inline Node *findRoot() {
Node *f = this;
f->access(), f->splay();
while (f->pushDown(), f->c[0] != null) f = f->c[0];
return f;
}
} pool[MAXN];
inline void init() {
null = pool, null->fa = null;
}
inline char nextChar() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}
inline int read() {
static int x = 0;
static char c;
for (x = 0, c = nextChar(); !isdigit(c); c = nextChar());
for (; isdigit(c); c = nextChar())
x = (x + (4 * x) << 1) + (c ^ '0');
return x;
}
char obuf[1000000], *oh = obuf;
int n, m;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
init();
n = read(); m = read();
char c;
for (register int i = 1; i <= n; i++) pool[i] = (Node) { null, null, null };
for (int i = 1; i <= m; ++i) {
while (c = nextChar(), c < 'A' || c > 'Z');
if (c == 'Q') {
if ((pool + read())->findRoot() == (pool + read())->findRoot()) {
*oh++ = 'Y', *oh++ = 'e', *oh++ = 's', *oh++ = '\n';
} else {
*oh++ = 'N', *oh++ = 'o', *oh++ = '\n';
}
} else if (c == 'C') {
(pool + read())->link(pool + read());
} else {
(pool + read())->cut(pool + read());
}
}
fwrite(obuf, 1, oh - obuf, stdout);
return 0;
}
分享到