洛谷P2147 [SDOI2008]Cave 洞穴勘测
2018-06-17 21:26:35来源:未知 阅读 ()
题目描述
辉辉热衷于洞穴勘测。
某天,他按照地图来到了一片被标记为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 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 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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:VS的 X64下的汇编编译
下一篇:类和对象应用例题
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash