SDOI2008 洞穴勘测

发表于
字数统计: 1,621 | 阅读时长 ≈ 7

前言

刚刚学会了LCT，找了一道很基础的题来练练手…
我好菜啊

题目

题目描述

辉辉热衷于洞穴勘测。

某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。 洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。

辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：

如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v

如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v

经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。

因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。 然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。

辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。 已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

输入输出格式

输入格式：

第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。 以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（”Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。

输出格式：

对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）

输入输出样例

输入样例#1：
200 5
Query 123 127
Connect 123 127
Query 123 127
Destroy 127 123
Query 123 127
输出样例#1：
No
Yes
No
输入样例#2：
3 5
Connect 1 2
Connect 3 1
Query 2 3
Destroy 1 3
Query 2 3
输出样例#2：
Yes
No

数据说明

10%的数据满足n≤1000, m≤20000

20%的数据满足n≤2000, m≤40000

30%的数据满足n≤3000, m≤60000

40%的数据满足n≤4000, m≤80000

50%的数据满足n≤5000, m≤100000

60%的数据满足n≤6000, m≤120000

70%的数据满足n≤7000, m≤140000

80%的数据满足n≤8000, m≤160000

90%的数据满足n≤9000, m≤180000

100%的数据满足n≤10000, m≤200000

保证所有Destroy指令将摧毁的是一条存在的通道

本题输入、输出规模比较大，建议c\c++选手使用scanf和printf进行I\O操作以免超时

解题

mmp题目好长啊
对于会LCT的人来说，这可能是一道纯的模板…
但是好像说，并查集更快？！
算了算了我还是直接贴出代码好了
开氧跑了808ms…

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
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
#define drep(i,a,b) for(re i=(a);i>=(b);--(i))

using namespace  std;

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

const int N=10010;
char s[10];
int n,m,x,y;
struct node{
    int ch[N][2],fa[N],tag[N],stk[N],top;
    inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
    inline void push_down(int x){
        if(tag[x]){
            tag[ch[x][0]]^=1;tag[ch[x][1]]^=1;
            swap(ch[x][0],ch[x][1]);tag[x]=0;
        }
    }
    inline void rotate(int x){
        re y=fa[x],z=fa[y],k=ch[y][1]==x;
        if(!isroot(y)) ch[z][ch[z][1]==y]=x;
        ch[y][k]=ch[x][k^1], fa[ch[x][k^1]]=y;
        ch[x][k^1]=y;fa[x]=z;fa[y]=x;
    }
    inline void splay(int x){
        stk[top=1]=x;for(re i=x;!isroot(i);i=fa[i]) stk[++top]=fa[i];
        drep(i,top,1) push_down(stk[i]);
        for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){
            if(!isroot(y)) ((ch[y][0]==x)^(ch[z][0]==y))?rotate(x):rotate(y);
            rotate(x);
        }
    }
    inline int access(int x){
        int t=0;
        while(x){
            splay(x);ch[x][1]=t;t=x;x=fa[x];
        }
        return t;
    }
    inline int find(int x){
        access(x);splay(x);int now=x;
        while(ch[now][0]) now=ch[now][0];
        return now;
    }
    inline void makeroot(int x){access(x);splay(x);tag[x]^=1;}
    inline void link(int x,int y){makeroot(x); if(find(x)!=find(y)) fa[x]=y;}
    inline void cut(int x,int y){
        makeroot(x);access(y);splay(y);
        if(fa[x]!=y||ch[x][1]) return;
        fa[x]=0;ch[y][0]=0;
    }
    inline bool query(int x,int y){return (find(x)==find(y))?1:0;}
}LCT;

int main(){
    n=read();m=read();
    while(m--){
        scanf("%s",s);x=read();y=read();
        if(s[0]=='C') LCT.link(x,y);
        else if(s[0]=='Q'){
            if(LCT.query(x,y)) puts("Yes");
            else puts("No");
        }
        else if(s[0]=='D') LCT.cut(x,y);
    }
    return 0;
}

后记

mmp大水题我修了好久但是感觉自己对于 splay-tree 和 LCT 会打了很多
我好菜啊…我觉得这篇博客意义不大但是我打的时间也少
欢迎指正…
以下本人联系方式

qq： 953559040

微博： IncinblePan

洛谷： SherlockPan