首页 > 代码库 > BZOJ1180: [CROATIAN2009]OTOCI
BZOJ1180: [CROATIAN2009]OTOCI
1180: [CROATIAN2009]OTOCI
Time Limit: 50 Sec Memory Limit: 162 MBSubmit: 408 Solved: 241
[Submit][Status]
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
题解:
要求在线处理所有操作,我就呵呵了。
代码:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 100000+5 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26 int x=0,f=1;char ch=getchar(); 27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 29 return x*f; 30 } 31 int n,m,v[maxn],sum[maxn],c[maxn][2],fa[maxn],f[maxn],sta[maxn],top; 32 bool rev[maxn]; 33 inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);} 34 inline bool isroot(int x) 35 { 36 return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; 37 } 38 inline void pushup(int x) 39 { 40 sum[x]=sum[c[x][0]]+sum[c[x][1]]+v[x]; 41 } 42 inline void rever(int x) 43 { 44 rev[x]^=1;swap(c[x][0],c[x][1]); 45 } 46 inline void pushdown(int x) 47 { 48 if(!rev[x])return; 49 rever(c[x][0]);rever(c[x][1]); 50 rev[x]=0; 51 } 52 inline void rotate(int x) 53 { 54 int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 55 if(!isroot(y))c[z][c[z][1]==y]=x; 56 fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 57 c[y][l]=c[x][r];c[x][r]=y; 58 pushup(y);pushup(x); 59 } 60 inline void splay(int x) 61 { 62 sta[++top]=x; 63 for(int y=x;!isroot(y);y=fa[y])sta[++top]=fa[y]; 64 for(;top;)pushdown(sta[top--]); 65 while(!isroot(x)) 66 { 67 int y=fa[x],z=fa[y]; 68 if(!isroot(y)) 69 { 70 if(c[z][0]==y^c[y][0]==x)rotate(x);else rotate(y); 71 } 72 rotate(x); 73 } 74 } 75 inline void access(int x) 76 { 77 for(int y=0;x;x=fa[x]) 78 { 79 splay(x);c[x][1]=y;pushup(x);y=x; 80 } 81 } 82 inline void makeroot(int x) 83 { 84 access(x);splay(x);rever(x); 85 } 86 inline void link(int x,int y) 87 { 88 if(find(x)==find(y)){printf("no\n");return;} 89 printf("yes\n"); 90 makeroot(x);fa[x]=y;f[find(x)]=find(y);splay(x); 91 } 92 inline void split(int x,int y) 93 { 94 makeroot(x);access(y);splay(y); 95 } 96 int main() 97 { 98 freopen("input.txt","r",stdin); 99 freopen("output.txt","w",stdout);100 n=read();101 for1(i,n)v[i]=sum[i]=read(),f[i]=i;102 m=read();103 while(m--)104 {105 char ch[10];106 scanf("%s",ch);int x=read(),y=read();107 if(ch[0]==‘b‘)link(x,y);108 else if(ch[0]==‘p‘)splay(x),v[x]=y,pushup(x);109 else if(find(x)!=find(y))printf("impossible\n");110 else split(x,y),printf("%d\n",sum[y]);111 }112 return 0;113 }
BZOJ1180: [CROATIAN2009]OTOCI
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。