洛谷P2147 [SDOI2008]Cave 洞穴勘测

题目描述

辉辉热衷于洞穴勘测。

某天,他按照地图来到了一片被标记为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: 

样例输入1 cave.in
200	5
Query	123	127
Connect	123	127
Query	123	127
Destroy	127	123
Query	123	127
样例输入2 cave.in

3 5
Connect	1	2
Connect	3	1
Query	2	3
Destroy	1	3
Query	2	3

输出样例#1:

样例输出1 cave.out
No
Yes
No


样例输出2 cave.out

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操作以免超时

LCT裸题

看了一下午,终于看明白点了

感觉LCT是个和玄学的东西

有空总结一下

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2*1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
    return x*f;
}
struct node
{
    int ch[2],fa;
    bool rev,IsRoot;
    node(){ch[0]=ch[1]=fa=rev=0;IsRoot=1;}
}T[MAXN];
int get(int x)
{
    if(T[ T[x].fa ].ch[1]==x) return 1;
    if(T[ T[x].fa ].ch[0]==x) return 0;
    return -1;
}
void PushReverse(int x)
{
    if(!T[x].rev) return ;
    T[x].rev=0;
    swap(T[x].ch[0],T[x].ch[1]);
    T[T[x].ch[0]].rev^=1;
    T[T[x].ch[1]].rev^=1;
}
void push(int x)
{
    if(get(x)!=-1) push(T[x].fa);
    PushReverse(x);
}
int connect(int x,int fa,int how)
{
    T[x].fa=fa;
    T[fa].ch[how]=x;
}
void rotate(int x)
{
    int Y=T[x].fa;
    int R=T[Y].fa;
    int Yson=get(x);
    int Rson=get(Y);
    int B=T[x].ch[Yson^1];
    T[x].fa=R;
    if(get(Y)!=-1)
    connect(x,R,Rson);
    connect(B,Y,Yson);
    connect(Y,x,Yson^1);
}
void splay(int x)
{
    push(x);
    for(int f=T[x].fa;get(x)!=-1;rotate(x),f=T[x].fa)
        if(get(f)!=-1) 
            rotate( get(f)==get(x)?f:x );
}
void access(int x)
{
    for(int t=0;x;x=T[t=x].fa)
        splay(x),T[x].ch[1]=t;
}
void MakeRoot(int x)
{
    access(x);
    splay(x);
    T[x].rev=1;
}
int link(int x,int y)
{
    MakeRoot(x);
    T[x].fa=y;
}
int cut(int x,int y)
{
    MakeRoot(x);
    access(y);
    splay(y);
    T[x].fa=T[y].ch[0]=0;
}
int find(int x)
{
    while(get(x)!=-1) x=T[x].fa;
    return x;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #else
    #endif
    int N=read(),M=read();
    while(M--)
    {
        char opt[10];int x,y;
        scanf("%s",opt);x=read(),y=read();
        if(opt[0]=='Q')
            find(x)==find(y)?printf("Yes\n"):printf("No\n");
        else if(opt[0]=='C')
            link(x,y);
        else if(opt[0]=='D')
            cut(x,y);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python tkinter版猜数游戏

程序启动后,首先需要启动一次游戏并设置数值范围和猜测次数,然后可以猜数并输入,程序会根据实际情况进行大小提示,退出程序时提示战绩,例如共玩几次和成功几次。 im...

44550
来自专栏章鱼的慢慢技术路

程序员算法时间空间复杂度速查表

16550
来自专栏黒之染开发日记

PIXI输出base64图像

如果想使用 canvas 原生的 toDataURL ,参考这篇问答,以下代码是具体方法。但这个方法如果在iOS设备上使用,获取到的图像会上下翻转(效果相当于c...

16610
来自专栏吉浦迅科技

DAY39:阅读扩展数据类型

15620
来自专栏Coding01

推荐一个制作「ASCII 流程图」工具——Graph Easy

我不止一次看到类似「知乎」网站那种 Console 上直接输出这种「ASCII 文本」。

22920
来自专栏码生

Swift2转Swift3

接触swift 已经有一年多的时间了,由最初的OC代码转为 swift 代码,然后从 swift 2.3 转为 swift 3。每次的转换都感觉是将项目整个的翻...

17750
来自专栏.net core新时代

我是怎么使用最短路径算法解决动态联动问题的

  省市县三级联动问题相信大家都耳熟能详了,选择市下拉选项依赖于省,同样的选择县下拉选项依赖于市。把省市县抽象成三个节点A(省),B(市),C(县),它们的关系...

33790
来自专栏牛客网

阿里技术一面,Java研发岗

之前过了个简单的简历面,过了几天后没打来以为凉了,然后昨晚又接到了电话,括号内容是回答说的,理解有限,不一定都对,欢迎纠正~加油每一个牛友们! 阿里一面: ...

47790
来自专栏FreeBuf

如何破解安卓手机上的图形锁(九宫格锁)

安卓手机的图形锁(九宫格)是3x3的点阵,按次序连接数个点从而达到锁定/解锁的功能。最少需要连接4个点,最多能连接9个点。网上也有暴力删除手机图形锁的方法,即直...

28270
来自专栏嵌入式程序猿

【电机控制不得不学习的干货:】 飞思卡尔MCU正交编/解码器模块

在电机控制领域,我们经常需要得到电机的转速,位置来执行算法,那么想知道转速是如何获得的吗?看过来,猿来你在这里O(∩_∩)O~ 正交编码器简介 飞思卡尔增强型正...

312110

扫码关注云+社区

领取腾讯云代金券