bzoj2049 [ SDOI2008 ] -- LCT
2018-06-17 23:09:15来源:未知 阅读 ()
只有cut和link操作的LCT
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 #define N 10010 6 int i,j,k,x,y,n,m,f[N],ch[N][2]; 7 bool r[N],b[N]; 8 char c[30]; 9 inline void Update(int x){ 10 if(x==0)return; 11 swap(ch[x][0],ch[x][1]); 12 r[x]^=1; 13 } 14 inline void Pushdown(int x){ 15 if(r[x]){ 16 Update(ch[x][0]); 17 Update(ch[x][1]); 18 r[x]=0; 19 } 20 } 21 inline int Get(int x){return ch[f[x]][1]==x;} 22 inline void Rotate(int x){ 23 bool d=Get(x);int y=f[x]; 24 if(b[y])b[x]=1,b[y]=0;else ch[f[y]][Get(y)]=x; 25 ch[y][d]=ch[x][d^1];f[ch[y][d]]=y; 26 f[x]=f[y];ch[x][d^1]=y;f[y]=x; 27 } 28 inline void P(int x){ 29 if(!b[x])P(f[x]); 30 Pushdown(x); 31 } 32 inline void Splay(int x){ 33 P(x); 34 for(;!b[x];Rotate(x)) 35 if(!b[f[x]])Rotate(Get(x)==Get(f[x])?f[x]:x); 36 } 37 inline void Access(int x){ 38 int y=0; 39 while(x){ 40 Splay(x); 41 b[ch[x][1]]=1;ch[x][1]=y;b[y]=0; 42 y=x;x=f[x]; 43 } 44 } 45 inline void mr(int x){Access(x);Splay(x);Update(x);} 46 inline int Find(int x){ 47 while(f[x])x=f[x]; 48 return x; 49 } 50 inline void Link(int x,int y){ 51 if(Find(x)==Find(y))return; 52 mr(x);f[x]=y; 53 } 54 inline void Cut(int x,int y){ 55 mr(x);Access(y);Splay(y); 56 f[ch[y][0]]=0;b[ch[y][0]]=1;ch[y][0]=0; 57 } 58 int main() 59 { 60 scanf("%d%d",&n,&m); 61 for(i=1;i<=n;i++)b[i]=1; 62 while(m--){ 63 scanf("%s%d%d",c,&x,&y); 64 if(c[0]=='C')Link(x,y);else 65 if(c[0]=='Q')if(Find(x)==Find(y))puts("Yes");else puts("No");else Cut(x,y); 66 } 67 return 0; 68 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ3669: [Noi2014]魔法森林(瓶颈生成树 LCT) 2018-07-09
- bzoj2002 [ HNOI2010 ] -- LCT 2018-06-17
- bzoj2843 -- LCT 2018-06-17
- bzoj2631 -- LCT 2018-06-17
- P1984 [SDOI2008]烧水问题 2018-06-17
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