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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2815][ZJOI2012]灾难  

2015-01-06 11:29:38|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2815: [ZJOI2012]灾难

完全不会做……

题目&题解
http://fanhq666.blog.163.com/blog/static/8194342620124274154996/
详细的题面直接去网上找浙江的数据包吧……

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 35524+100;
int n,m,du[N],size[N];
int scan(){int i=0;scanf("%d",&i);return i;}
struct Node{
Node();
Node *ch[2],*fa;int flag,d;
bool pl(){return this == fa->ch[1];flag=0;}
void push();
}*null,lnode[N];
Node::Node(){ch[0]=ch[1]=fa=null;}
void Node::push(){
if(flag){
swap(ch[0],ch[1]);
ch[0]->flag^=1;
ch[1]->flag^=1;
flag=0;
}
}
struct LCT{
LCT(){
if(!null){
null = new Node();
*null = Node();
}
}
bool notr(Node *r){return r->fa->ch[0]==r || r->fa->ch[1]==r;}
void rotate(Node *k){
Node *r = k->fa;if(r==null||k==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;
}
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 *hello(Node *r){
Node *l = null;
for(;r!=null;l=r,r=r->fa){
splay(r);
(r->ch[1]=l)->fa = r;
//r->count();
}return l;
}
void changer(Node *r){
hello(r)->flag^=1;
splay(r);
}
void link(Node *r,Node *l){
changer(r);
r->fa = l;
//splay(r);//!!!
hello(r);//*
}
void cut(Node *r,Node *l){//?
changer(r);
hello(l);
splay(r);
r->ch[1]=l->fa=null;
}
int lca(Node *r,Node *l,Node *ro){
changer(ro);
hello(r);
return hello(l)->d;
}
}lt;
struct Point{
Point(){next = NULL;}
int d;Point*next;
void push(int a){
Point *l = new Point;
l->d = a;
l->next = next;next=l;
}
}point[N],tree[N],eat[N];
void link(int a,int b){
//printf("%d->%d\n",a,b);
lt.link(&lnode[a],&lnode[b]);
tree[a].push(b);
}
queue<int>dui;
void dfs(int x){
size[x]=1;
for(Point *i = tree[x].next;i!=NULL;i=i->next){
dfs(i->d);
size[x] += size[i->d];
}
}
int main(){
int i,j,a;
//freopen("in.txt","r",stdin);
n = scan();
for(i=1;i<=n+1;i++)lnode[i] = Node(),lnode[i].d=i;
for(i=1;i<=n;i++){
a = scan();
while(a){
point[a].push(i);
eat[i].push(a);
du[i]++;
a = scan();
}
if(!du[i]){
eat[i].push(n+1);
dui.push(i);
//printf("%d\n",i);
}
}
while(!dui.empty()){
int now = dui.front();dui.pop();
//printf("%d ",now);
//each eat
a = eat[now].next->d;
for(Point *l = eat[now].next;l!=NULL;l=l->next)
a = lt.lca(&lnode[a],&lnode[l->d],&lnode[n+1]);
//printf("[%d]\n",a);
link(a,now);
//each hunter
for(Point *l = point[now].next;l!=NULL;l=l->next){
du[l->d]--;
if(!du[l->d])dui.push(l->d);
}
}
dfs(n+1);
for(i=1;i<=n;i++)
printf("%d\n",size[i]-1);
return 0;
}

真的是被fhq的题解逗了……
完全没有必要结果写了LCT= =、其实直接写倍增就行了
嘛就当复习了……
  评论这张
 
阅读(513)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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