分站城市网站如何做seo,域名备案,青岛百度优化,音乐网站需求分析题目描述 辉辉热衷于洞穴勘测。 某天#xff0c;他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测#xff0c;辉辉发现这片区域由n个洞穴#xff08;分别编号为1到n#xff09;以及若干通道组成#xff0c;并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通… 题目描述 辉辉热衷于洞穴勘测。 某天他按照地图来到了一片被标记为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行依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串sConnect”、”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.in3 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.outYes
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操作以免超时 这题比模板题还简单 不需要维护很多东西 查询时只要用pre往上走就行了看能否走到同一点 数据很小完全没问题 1 #includeiostream2 #includecstdio3 #includecstring4 #includealgorithm5 #includecmath6 #includequeue7 using namespace std;8 int ch[300005][2],pre[300005],n,m;9 bool isrt[300005],rev[300005];10 void pushdown(int o)11 {12 if (!o) return;13 if (rev[o])14 {15 int lsch[o][0],rsch[o][1];16 if (ls)17 {18 rev[ls]^1;19 swap(ch[ls][0],ch[ls][1]);20 }21 if (rs)22 {23 rev[rs]^1;24 swap(ch[rs][0],ch[rs][1]);25 }26 rev[o]0;27 }28 }29 void push(int o)30 {31 if (isrt[o]0)32 push(pre[o]);33 pushdown(o);34 }35 void rotate(int o,bool kind)36 {37 int ppre[o];38 ch[p][!kind]ch[o][kind];pre[ch[o][kind]]p;39 if (isrt[p]) isrt[o]1,isrt[p]0;40 else ch[pre[p]][ch[pre[p]][1]p]o;41 pre[o]pre[p];42 ch[o][kind]p;pre[p]o;43 }44 void splay(int o)45 {46 push(o);47 while (isrt[o]0)48 {49 if (isrt[pre[o]])50 rotate(o,ch[pre[o]][0]o);51 else52 {53 int ppre[o],kindch[pre[p]][0]p;54 if (ch[p][kind]o)55 rotate(o,!kind),rotate(o,kind);56 else rotate(p,kind),rotate(o,kind);57 }58 }59 }60 void access(int o)61 {62 int y0;63 while (o)64 {65 splay(o);66 isrt[ch[o][1]]1;isrt[ch[o][1]y]0;67 opre[yo];68 }69 }70 void makeroot(int o)71 {72 access(o);73 splay(o);74 rev[o]^1;75 swap(ch[o][0],ch[o][1]);76 }77 void link(int x,int y)78 {79 makeroot(x);80 pre[x]y;81 }82 void cut(int x,int y)83 {84 makeroot(x);access(y);splay(y);85 pre[x]0;86 ch[y][0]0;87 isrt[x]1;88 }89 void query(int x,int y)90 {91 while (pre[x]!0) xpre[x];92 while (pre[y]!0) ypre[y];93 if (xy) printf(Yes\n);94 else printf(No\n);95 }96 int main()97 {int i,c,x,y;98 char s[12];99 cinnm;
100 for (i1;in;i)
101 isrt[i]1;
102 for (i1;im;i)
103 {
104 scanf(%s%d%d,s,x,y);
105 if (s[0]Q)
106 {
107 query(x,y);
108 }
109 else if (s[0]C)
110 {
111 link(x,y);
112 }
113 else if (s[0]D)
114 {
115 cut(x,y);
116 }
117 }
118 } 转载于:https://www.cnblogs.com/Y-E-T-I/p/8296702.html
