首页 > 代码库 > OTOCI(bzoj 1180)
OTOCI(bzoj 1180)
Description
给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作: 1、bridge A B:询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”,并且在结点A和结点B之间连一条无向边。 2、penguins A X:将结点A对应的权值wA修改为X。 3、excursion A B:如果结点A和结点B不连通,则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。给出q个操作,要求在线处理所有操作。数据范围:1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。
Input
第一行包含一个整数n(1<=n<=30000),表示节点的数目。第二行包含n个整数,第i个整数表示第i个节点初始时对应的权值。第三行包含一个整数q(1<=n<=300000),表示操作的数目。以下q行,每行包含一个操作,操作的类别见题目描述。任意时刻每个节点对应的权值都是1到1000的整数。
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
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
impossible
yes
6
yes
yes
15
yes
15
16
#include<cstdio> #include<iostream> #define N 30010 using namespace std; int fa[N],son[N][2],rev[N],v[N],sum[N],st[N],n,m; bool isroot(int x){ return son[fa[x]][0]!=x&&son[fa[x]][1]!=x; } void pushup(int x){ sum[x]=sum[son[x][0]]+sum[son[x][1]]+v[x]; } void pushdown(int x){ if(!rev[x]) return; rev[son[x][0]]^=1;rev[son[x][1]]^=1; swap(son[x][0],son[x][1]);rev[x]=0; } void rotate(int x){ int y=fa[x],z=fa[y],l,r; if(son[y][0]==x) l=0;else l=1;r=l^1; if(!isroot(y)){ if(son[z][0]==y) son[z][0]=x; else son[z][1]=x; } fa[x]=z;fa[y]=x;fa[son[x][r]]=y; son[y][l]=son[x][r];son[x][r]=y; pushup(y);pushup(x); } void splay(int x){ int top=0;st[++top]=x; for(int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i]; for(int i=top;i;i--) pushdown(st[i]); while(!isroot(x)){ int y=fa[x],z=fa[y]; if(!isroot(y)){ if((son[z][0]==y)^(son[y][0]==x)) rotate(x); else rotate(y); } rotate(x); } } void access(int x){ int t=0; while(x){ splay(x); son[x][1]=t; pushup(x); t=x;x=fa[x]; } } void makeroot(int x){ access(x); splay(x); rev[x]^=1; } void join(int x,int y){ makeroot(x); fa[x]=y; splay(x); } void cut(int x,int y){ makeroot(x); access(x); splay(x); son[y][0]=fa[x]=0; pushup(y); } int find(int x){ access(x);splay(x); while(son[x][0]) x=son[x][0]; return x; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&v[i]); sum[i]=v[i]; } scanf("%d",&m); char opt[20];int x,y; for(int i=1;i<=m;i++){ scanf("%s%d%d",opt,&x,&y); if(opt[0]==‘b‘){ if(find(x)!=find(y)){ printf("yes\n"); join(x,y); } else printf("no\n"); } else if(opt[0]==‘p‘){ makeroot(x);v[x]=y; pushup(x); } else { if(find(x)==find(y)){ makeroot(x); access(y); splay(y); printf("%d\n",sum[y]); } else printf("impossible\n"); } } return 0; }
OTOCI(bzoj 1180)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。