bzoj 4229 选择

网友投稿 719 2022-08-29

bzoj 4229 选择

bzoj 4229 选择

​​ Description

现在，我想知道自己是否还有选择。 给定n个点m条边的无向图以及顺序发生的q个事件。 每个事件都属于下面两种之一： 1、删除某一条图上仍存在的边 2、询问是否存在两条边不相交的路径可以从点u出发到点v Input

第一行三个整数n,m,q 接下来m行，每行两个整数u,v，表示u和v之间有一条边 接下来q行，每行一个大写字母o和2个整数u、v，依次表示按顺序发生的q个事件： 当o为’Z’时，表示删除一条u和v之间的边 当o为’P’时，表示询问是否存在两条边不相交的路径可以从点u出发到点v Output

对于每组询问，如果存在，输出Yes,否则输出No Sample Input

7 8 7 1 2 1 3 1 4 2 3 3 4 3 7 7 4 5 6 Z 1 4 P 1 3 P 2 4 Z 1 3 P 1 3 Z 6 5 P 5 6 Sample Output

Yes Yes No No HINT

对于全部数据，max(n,m,q)<=100000 删边 不好做 改为离线 变成加边 然后动态维护边双联通分量即可 ​

#include#include#include#include#include#define pa pairusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;map mm;map:: iterator it;int fa[N],fa1[N],fa2[N],n,m,Q,c[N][2],q[N],top,cnt;bool rev[N];inline int find1(int x){ while(x!=fa1[x]) x=fa1[x]=fa1[fa1[x]];return x;}inline int find2(int x){ while(x!=fa2[x]) x=fa2[x]=fa2[fa2[x]];return x;}inline bool isroot(int x){ return c[find2(fa[x])][0]!=x&&c[find2(fa[x])][1]!=x;}inline void pushdown(int x){ if (!rev[x]) return;rev[x]^=1;int l=c[x][0],r=c[x][1]; rev[l]^=1;rev[r]^=1;swap(c[x][0],c[x][1]);}inline void rotate(int x){ int y=find2(fa[x]),z=find2(fa[y]),l=c[y][1]==x,r=l^1; if (!isroot(y)) c[z][c[z][1]==y]=x; fa[c[x][r]]=y;fa[y]=x;fa[x]=z; c[y][l]=c[x][r];c[x][r]=y;}inline void splay(int x){ q[top=1]=x;for (int i=x;!isroot(i);i=find2(fa[i])) q[++top]=find2(fa[i]); while(top) pushdown(q[top--]); while(!isroot(x)){ int y=find2(fa[x]),z=find2(fa[y]); if (!isroot(y)){ if (c[y][0]==x^c[z][0]==y) rotate(x);else rotate(y); }rotate(x); }}inline void access(int x){ for (int t=0;x;t=x,x=find2(fa[x])) splay(x),c[x][1]=t;}inline void makeroot(int x){ access(x); splay(x); rev[x]^=1;}inline void link(int x,int y){ fa1[find1(x)]=find1(y); makeroot(x);fa[x]=y;}inline void dfs(int x,int f){ fa2[x]=f;if (c[x][0]) dfs(c[x][0],f);if (c[x][1]) dfs(c[x][1],f);}inline void insert1(int x,int y){ x=find2(x);y=find2(y);if (x==y) return; if (find1(x)!=find1(y)) {link(x,y);return;} makeroot(x); access(y); splay(y); dfs(c[y][0],y);}struct node{int x,y,op,id;}qr[N];// op=0? print:delbool ans[N];int main(){ freopen("bzoj4229.in","r",stdin); n=read();m=read();Q=read(); for (int i=1;i<=n;++i) fa1[i]=fa2[i]=i; for (int i=1;i<=m;++i){ static int x,y;x=read();y=read(); if (x>y) swap(x,y);++mm[make_pair(x,y)]; } for (int i=1;i<=Q;++i){ static char ch;static int x,y; ch=gc();while(ch!='Z'&&ch!='P') ch=gc(); if (ch=='P')qr[i].x=read(),qr[i].y=read(),qr[i].op=0,qr[i].id=++cnt; else{ x=read();y=read();if (x>y) swap(x,y);--mm[make_pair(x,y)]; qr[i].op=1;qr[i].x=x;qr[i].y=y; } } for (it=mm.begin();it!=mm.end();++it){static int tim,x,y; tim=it->second;x=it->first.first;y=it->first.second;// printf("%d %d %d\n",tim,x,y); for (int j=1;j<=tim;++j) insert1(x,y); }// printf("%d %d %d\n",find2(3),find2(4),find2(7)); for (int i=Q;i;--i){ if (!qr[i].op) ans[qr[i].id]=(find2(qr[i].x)==find2(qr[i].y)); else insert1(qr[i].x,qr[i].y); } for (int i=1;i<=cnt;++i) ans[i]?puts("Yes"):puts("No"); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：数据
上一篇:你知道如何用PHP实现多进程吗？（php怎么启动多个进程）
下一篇:uoj 79 一般图最大匹配 苏凯树
相关文章

 发表评论

暂时没有评论，来抢沙发吧~