注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2049][Sdoi2008]Cave 洞穴勘测  

2014-11-30 20:23:01|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2049: [Sdoi2008]Cave 洞穴勘测

LCT复习
果然适当留下点裸题以后刷是正确的
因为太裸了没有题解

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m;
const int N = 10000+100;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n'||cc==9)cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
struct Node{
Node();
short flag;
Node *fa,*ch[2];
short pl(){return this == fa->ch[1];}
void push();
}*null,point[N];
Node::Node(){fa=ch[0]=ch[1]=null;flag=0;}
void Node::push(){
if(null == this)return;
if(flag){
swap(ch[0],ch[1]);
ch[0]->flag^=1;
ch[1]->flag^=1;
flag=0;
}
}
struct LCT{
LCT(){
null = new Node();
*null = Node();
}
bool notr(Node *r){return r==r->fa->ch[0] || r==r->fa->ch[1];}//!
void rotate(Node *k){
Node *r = k->fa;if(k==null||r==null)return;
r->push();k->push();
int x = k->pl()^1;
r->ch[x^1] = k->ch[x];
r->ch[x^1]->fa =r;
if(r->fa!=null && notr(r))r->fa->ch[r->pl()]=k;
k->fa = r->fa;r->fa =k;
k->ch[x] = r;
//count
}
void splay(Node *r){
for(;notr(r);rotate(r))
if(notr(r->fa))rotate(r->fa->pl()==r->pl()?r->fa:r);
r->push();//!!!!
}
Node *root(Node *r){
hello(r);splay(r);
while(r->ch[0]!=null)r=r->ch[0];
return r;
}
Node *hello(Node *r){
Node *l = null;
for(;r!=null;l=r,r=r->fa){
splay(r);
(r->ch[1] = l)->fa = r;//!
//count
}return l;
}
Node *changer(Node *r){
hello(r)->flag^=1;
splay(r);
}
Node *cut(Node *r,Node *l){
changer(r);
hello(l);splay(l);
l->ch[0] = r->fa = null;
}
Node *link(Node *r,Node *l){
changer(r);
r->fa = l;
hello(r);
}
}lt;
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;char com[10];
n = scan();m = scan();
for(i=1;i<=n;i++)point[i] = Node();
for(i=1;i<=m;i++){
scanf("%s",com);
a = scan();b = scan();
//printf("[%d]\n",i);
switch(com[0]){
case 'C':{
lt.link(&point[a],&point[b]);
break;
}
case 'D':{
lt.cut(&point[a],&point[b]);
break;
}
case 'Q':{
if(lt.root(&point[a])==lt.root(&point[b]))printf("Yes\n");
else printf("No\n");
break;
}
}
}
return 0;
}


  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017