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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2843/1180]极地旅行社  

2015-02-23 15:08:42|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2843: 极地旅行社

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 111  Solved: 70
[Submit][Status]

Description

不久之前,Mirko建立了一个旅行社,名叫“极地之梦”。这家旅行社在北极附近购买了N座冰岛,并且提供观光服务。当地最受欢迎的当然是帝企鹅了,这些小家伙经常成群结队的游走在各个冰岛之间。
Mirko的旅行社遭受一次重大打击,以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥,并用观光巴士来运载游客。Mirko希望开发一个电脑程序来管理这些大桥的建造过程,以免有不可预料的错误发生。
这些冰岛从1到N标号。一开始时这些岛屿没有大桥连接,并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变,但是始终在[0, 1000]之间。
你的程序需要处理以下三种命令:
1."bridge A B"——在A与B之间建立一座大桥(A与B是不同的岛屿)。由于经费限制,这项命令被接受,当且仅当A与B不联通。若这项命令被接受,你的程序需要输出"yes",之后会建造这座大桥。否则,你的程序需要输出"no"。
2."penguins A X"——根据可靠消息,岛屿A此时的帝企鹅数量变为X。这项命令只是用来提供信息的,你的程序不需要回应。
3."excursion A B"——一个旅行团希望从A出发到B。若A与B连通,你的程序需要输出这个旅行团一路上所能看到的帝企鹅数量(包括起点A与终点B),若不联通,你的程序需要输出"impossible"。

Input

第一行一个正整数N,表示冰岛的数量。

第二行N个范围[0, 1000]的整数,为每座岛屿初始的帝企鹅数量。

第三行一个正整数M,表示命令的数量。

接下来M行即命令,为题目描述所示。

Output

对于每个bridge命令与excursion命令,输出一行,为题目描述所示。

Sample Input

5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5

Sample Output

4
impossible
yes
6
yes
yes
15
yes
15
16

HINT

1<=N<=30000
1<=M<=100000

Solution

唉,裸的LCT。连cut都没有。
为什么修改完权值之后还要makeroot一下呢?我觉得是用来清标记用的。不然会Wa

Code

/**************************************************************
    Problem: 2843
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1212 ms
    Memory:1628 kb
****************************************************************/
 
#include<cstdio>
const int N=30010;
int rev[N],far[N],son[N][2],val[N],swap_tmp,sum[N],fa[N],n,m,x,y,i;
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
bool not_root(int t){
    return son[far[t]][0]==t||son[far[t]][1]==t;
}
void push_up(int t){
    sum[t]=sum[son[t][0]]+sum[son[t][1]]+val[t];
}
void push_down(int t){
    rev[t]?rev[t]=0,rev[son[t][0]]^=1,rev[son[t][1]]^=1,
    swap_tmp=son[t][0],son[t][0]=son[t][1],son[t][1]=swap_tmp:1;
}
void rotate(int t){
    int f=far[t],p=son[f][1]==t;
    far[t]=far[f],not_root(f)?son[far[f]][son[far[f]][1]==f]=t:1,
    (son[f][p]=son[t][!p])?far[son[f][p]]=f:1,
    push_up(son[far[f]=t][!p]=f);
}
void preview(int t){
    if(not_root(t))preview(far[t]);
    push_down(t);
}
void splay(int t,int f=0){
    for(preview(t);not_root(t);rotate(t))
    not_root(f=far[t])?rotate((son[f][1]==t^son[far[f]][1]==f?t:f)),1:1;
    push_up(t);
}
void access(int t,int las=0){
    for(;t;splay(t),son[t][1]=las,las=t,t=far[t]);
}
void makeroot(int t){
    access(t),splay(t),rev[t]^=1;
}
void link(int u,int v){
    makeroot(u),far[u]=v,fa[gf(u)]=gf(v);
}
void cut(int u,int v){
    makeroot(u),access(v),splay(v),son[v][0]=far[u]=0;
}
int aa;char ch,op;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
int main(){
    for(n=F(),i=1;i<=n;i++)val[i]=F(),fa[i]=i;
    for(m=F();m--;){
        while(op=getchar(),op<'a'||op>'z');x=F(),y=F();
        if(op=='e'){
            if(gf(x)!=gf(y))puts("impossible");
            else{
                makeroot(x),access(y),splay(y),printf("%d\n",sum[y]);
            }
        }
        else if(op=='b'){
            if(gf(x)==gf(y))puts("no");
            else puts("yes"),link(x,y);
        }
        else{
            val[x]=y;makeroot(x);
        }
    }
}
  评论这张
 
阅读(60)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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