題目描述

輝輝熱衷于洞穴勘測(cè)。

某天，他按照地圖來到了一片被標(biāo)記為JSZX的洞穴群地區(qū)。經(jīng)過初步勘測(cè)，輝輝發(fā)現(xiàn)這片區(qū)域由n個(gè)洞穴（分別編號(hào)為1到n）以及若干通道組成，并且每條通道連接了恰好兩個(gè)洞穴。假如兩個(gè)洞穴可以通過一條或者多條通道按一定順序連接起來，那么這兩個(gè)洞穴就是連通的，按順序連接在一起的這些通道則被稱之為這兩個(gè)洞穴之間的一條路徑。 洞穴都十分堅(jiān)固無法破壞，然而通道不太穩(wěn)定，時(shí)常因?yàn)橥饨缬绊懚l(fā)生改變，比如，根據(jù)有關(guān)儀器的監(jiān)測(cè)結(jié)果，123號(hào)洞穴和127號(hào)洞穴之間有時(shí)會(huì)出現(xiàn)一條通道，有時(shí)這條通道又會(huì)因?yàn)槟撤N稀奇古怪的原因被毀。

輝輝有一臺(tái)監(jiān)測(cè)儀器可以實(shí)時(shí)將通道的每一次改變狀況在輝輝手邊的終端機(jī)上顯示：

如果監(jiān)測(cè)到洞穴u和洞穴v之間出現(xiàn)了一條通道，終端機(jī)上會(huì)顯示一條指令 Connect u v

如果監(jiān)測(cè)到洞穴u和洞穴v之間的通道被毀，終端機(jī)上會(huì)顯示一條指令 Destroy u v

經(jīng)過長(zhǎng)期的艱苦卓絕的手工推算，輝輝發(fā)現(xiàn)一個(gè)奇怪的現(xiàn)象：無論通道怎么改變，任意時(shí)刻任意兩個(gè)洞穴之間至多只有一條路徑。

因而，輝輝堅(jiān)信這是由于某種本質(zhì)規(guī)律的支配導(dǎo)致的。因而，輝輝更加夜以繼日地堅(jiān)守在終端機(jī)之前，試圖通過通道的改變情況來研究這條本質(zhì)規(guī)律。 然而，終于有一天，輝輝在堆積成山的演算紙中崩潰了……他把終端機(jī)往地面一砸（終端機(jī)也足夠堅(jiān)固無法破壞），轉(zhuǎn)而求助于你，說道：“你老兄把這程序?qū)憣懓伞薄?/p>

輝輝希望能隨時(shí)通過終端機(jī)發(fā)出指令 Query u v，向監(jiān)測(cè)儀詢問此時(shí)洞穴u和洞穴v是否連通。現(xiàn)在你要為他編寫程序回答每一次詢問。 已知在第一條指令顯示之前，JSZX洞穴群中沒有任何通道存在。

輸入輸出格式

輸入格式：

第一行為兩個(gè)正整數(shù)n和m，分別表示洞穴的個(gè)數(shù)和終端機(jī)上出現(xiàn)過的指令的個(gè)數(shù)。 以下m行，依次表示終端機(jī)上出現(xiàn)的各條指令。每行開頭是一個(gè)表示指令種類的字符串s（"Connect”、”Destroy”或者”Query”，區(qū)分大小寫），之后有兩個(gè)整數(shù)u和v (1≤u, v≤n且u≠v) 分別表示兩個(gè)洞穴的編號(hào)。

輸出格式：

對(duì)每個(gè)Query指令，輸出洞穴u和洞穴v是否互相連通：是輸出”Yes”，否則輸出”No”。（不含雙引號(hào)）

輸入輸出樣例

輸入樣例#1： 復(fù)制 樣例輸入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： 復(fù)制 樣例輸出1 cave.out No Yes No樣例輸出2 cave.outYes No

說明

數(shù)據(jù)說明

10%的數(shù)據(jù)滿足n≤1000, m≤20000

20%的數(shù)據(jù)滿足n≤2000, m≤40000

30%的數(shù)據(jù)滿足n≤3000, m≤60000

40%的數(shù)據(jù)滿足n≤4000, m≤80000

50%的數(shù)據(jù)滿足n≤5000, m≤100000

60%的數(shù)據(jù)滿足n≤6000, m≤120000

70%的數(shù)據(jù)滿足n≤7000, m≤140000

80%的數(shù)據(jù)滿足n≤8000, m≤160000

90%的數(shù)據(jù)滿足n≤9000, m≤180000

100%的數(shù)據(jù)滿足n≤10000, m≤200000

保證所有Destroy指令將摧毀的是一條存在的通道

本題輸入、輸出規(guī)模比較大，建議c\c++選手使用scanf和printf進(jìn)行I\O操作以免超時(shí)

這題比模板題還簡(jiǎn)單

不需要維護(hù)很多東西

查詢時(shí)只要用pre往上走就行了，看能否走到同一點(diǎn)

數(shù)據(jù)很小，完全沒問題

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 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 ls=ch[o][0],rs=ch[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 p=pre[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 else 52 { 53 int p=pre[o],kind=ch[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 y=0; 63 while (o) 64 { 65 splay(o); 66 isrt[ch[o][1]]=1;isrt[ch[o][1]=y]=0; 67 o=pre[y=o]; 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) x=pre[x]; 92 while (pre[y]!=0) y=pre[y]; 93 if (x==y) printf("Yes\n"); 94 else printf("No\n"); 95 } 96 int main() 97 {int i,c,x,y; 98 char s[12]; 99 cin>>n>>m; 100 for (i=1;i<=n;i++) 101 isrt[i]=1; 102 for (i=1;i<=m;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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Y-E-T-I/p/8296702.html

總結(jié)

以上是生活随笔為你收集整理的[SDOI2008]Cave 洞穴勘测的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。