题目
链接
[SDOI2008]洞穴勘测
题意简述
使 个节点的一棵树支持 3种操作：
思路
暴力并查集
这很明显就是维护动态森林吧。
每次操作前先将$x$ 提根。
连接时将 设为 的父亲。
断开时将 的父亲设为 。
暴力查询。
玄学复杂度。
时间复杂度： 。
不过据说是随机数据所以跑得比香港记者还快。
LCT
我太蒻了，学了再补全。
代码
暴力并查集
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
|
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) < (z); ++(x))
const int kmax_num = 1e4+ 10, kmax_int = 2147483647, kmod = 1e9+7;
int n, m;
int f[kmax_num];
inline void (REG int x) {
for(REG int a = 0, fa = f[x]; x; fa = f[x])
f[x] = a, a = x, x = fa;
return ;
}
int main() {
std::cin >> n >> m;
REG char cmd;
REG int u, v;
FOR(i,0,m) {
while(!isalpha(cmd = getchar())) continue;
std::cin >> u >> v;
SPlay(u);
if(cmd == 'C') f[u] = v;
else if(cmd == 'D') f[v] = 0;
else {
for( ; u != v && v; v = f[v]) continue;
puts(u == v ? "Yes" : "No");
}
}
return 0;
}
|
杂项
近期评论