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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2594][Wc2006]水管局长数据加强版  

2014-08-28 12:25:09|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2594: [Wc2006]水管局长数据加强版

正式的LCT第一题(之前那个弹飞绵羊不算
学习+调试花了n天(n>=3 我也不知道为啥我这么弱)
主要原因是我自己的代码风格比较傻逼
然后抄代码的时候各种不注意细节
今天早上总算过掉了QAQ

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 100000+10;
const int M = 1000000 +10;
const int Q = N;
int n,m,q;
int fa[N],size[N],ask[Q][3],ans[Q];
short del[M];
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')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();
int d,bh;short flag;
Node *fa,*ch[2],*best;
bool pl(){return this==fa->ch[0]?0:1;}
void push();void count();
}*null,house[M],point[N];
void print(Node *r,int deep=0){
r->push();
for(int i=1;i<=deep;i++) printf(" ");
printf("[%d fa:%d b:%d bh:%d ,flag %c]\n",r->d,r->fa->d,r->best->d,r->bh,r->flag?'T':'F');
for(int i=1;i<=deep;i++) printf(" ");
printf("ch[0]\n");
if(r->ch[0]!=null)print(r->ch[0],deep+1);
for(int i=1;i<=deep;i++) printf(" ");
printf("ch[1]\n");
if(r->ch[1]!=null)print(r->ch[1],deep+1);
}
int hn;
queue<Node*>pupa;
Node* newNode(){
if(hn < M){house[hn]=Node();house[hn].best = &house[hn];return &house[hn++];}
if(pupa.empty())return new Node();
Node *r = pupa.front();pupa.pop();
*r = Node();r->best = r;return r;return new Node();
}
void dele(Node *&r){pupa.push(r);r=null;}
Node::Node(){d=flag=bh=0;fa=ch[0]=ch[1]=null;best = this;}
void Node::push(){
if(this==null)return;
if(flag){
swap(ch[0],ch[1]);
ch[0]->flag^=1;
ch[1]->flag^=1;
flag=0;
}
}
void Node::count(){
if(this==null)return;
best=this;
if(ch[0]->best->d > best->d)best=ch[0]->best;
if(ch[1]->best->d > best->d)best=ch[1]->best;
}
struct LCT{
LCT(){
null = newNode();
null -> ch[0]=null->ch[1]=null->fa = null;
//null->best = null;
}
bool notr(Node *r){return r==r->fa->ch[0]||r==r->fa->ch[1];}
void rotate(Node *k){
Node *r = k->fa;if(r==null||k==null)return;
r->fa->push();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;
r->count();k->count();
}
void splay(Node *r){
for(;notr(r);rotate(r))
if(notr(r->fa))rotate(r->fa->pl()==r->pl()?r->fa:r);
}
Node *hello(Node *r){
Node *l = null;
for(;r!=null;l=r,r=r->fa){
splay(r);
r->push();
r->ch[1] = l;
l->fa = r;//*
r->count();
}return l;
}
void changer(Node *r){
hello(r)->flag^=1;
splay(r);
}
void cut(Node *r,Node *l){
changer(r);
hello(l);
splay(l);
l->ch[0]=r->fa = null;
l->count();
}
void link(Node *r,Node *l){
changer(r);
r->fa = l;
hello(r);
}
Node *ask(int a,int b){
Node *r = &point[a],*l = &point[b];
changer(r);
hello(l);
splay(l);
//l->count();
return l->best;
}
}lt;
struct Edge{
int a,b,c;
Edge(){}
Edge(int aa,int bb,int cc):a(aa),b(bb),c(cc){if(a>b)swap(a,b);}
}edges[M],back[M];
bool operator < (Edge a,Edge b){if(a.a==b.a)return a.b<b.b;return a.a<b.a;}
bool operator == (Edge a,Edge b){return a.a==b.a&&a.b==b.b;}
bool cmp(Edge a,Edge b){return a.c<b.c;}
int find(int x){if(!fa[x])return x;return fa[x]=find(fa[x]);}
bool merge(int a,int b){
int ffa=find(a),ffb=find(b);
if(ffa==ffb)return 0;
if(size[ffa] > size[ffb])swap(ffa,ffb);
fa[ffa] = ffb;size[ffb]+=size[ffa];
return 1;
}
int finde(Edge e){
int l=1,r=m;
while(l<r){
int mid = (l+r)/2;
if(e==edges[mid])return mid;
else if(e<edges[mid]) r=mid-1;
else l=mid+1;
}return l;
}
int main(){
int i,j,a,b,c;
n=scan();m=scan();q=scan();
for(i=1;i<=n;i++){point[i]=Node();point[i].best=&point[i];point[i].d = -i;}
for(i=1;i<=m;i++){
a=scan();b = scan();c=scan();
edges[i]=back[i] = Edge(a,b,c);
}
sort(edges+1,edges+1+m);
sort(back+1,back+1+m,cmp);
for(i=1;i<=q;i++){
ask[i][0]=scan();
ask[i][1]=scan();
ask[i][2]=scan();
if(ask[i][1] > ask[i][2])swap(ask[i][1],ask[i][2]);
if(ask[i][0]==2)del[finde(Edge(ask[i][1],ask[i][2],0))] = 1;
}
for(i=1;i<=m;i++)
if(!del[j=finde(Edge(back[i].a,back[i].b,0))]&&merge(back[i].a,back[i].b)){
Node *r = newNode();r->d = back[i].c;r->bh=j;
lt.link(r,&point[back[i].a]);
lt.link(r,&point[back[i].b]);
}
for(i=q;i;i--){
a = ask[i][1];b=ask[i][2];
if(ask[i][0]==1){
ans[++ans[0]] = lt.ask(a,b)->d;
}else{
Node *r = lt.ask(a,b);
j = finde(Edge(a,b,0));
if(edges[j].c < r->d){
lt.cut(r,&point[edges[r->bh].a]);
lt.cut(r,&point[edges[r->bh].b]);
dele(r);
r = newNode();
r->bh = j;r->d = edges[j].c;
lt.link(r,&point[a]);
lt.link(r,&point[b]);
}
}
}
for(i=ans[0];i;i--)
printf("%d\n",ans[i]);
return 0;
}

题解:
离线后倒着用lct动态维护mst
  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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