首页 > 代码库 > bzoj4668: 冷战 并查集
bzoj4668: 冷战 并查集
并查集，按秩合并，树高log，暴力查询。
果然bzoj新挂的题中过的人多的全是sb题。
写了一发秒WA，发现姿势不对。(@_@)
然后过了50min，开始怀疑人生。(*_*)
这么长时间我lct都写完了。(Q_Q)
本着凡事要往好处想的精神，至少我改正了姿势。(T_T)
#include<cstdio>#define N 500005int n,m,q,k,s,t,l;int f[N],d[N],r[N],p[N];int find(int i){ if(p[i]==i) return i; int j=find(p[i]); return d[i] =d[p[i]]+1,j;}int join(int i,int j){ if((i=find(i)) ==(j=find(j))) return 0; if(r[i]>r[j]) i^=j,j^=i,i^=j; if(r[i]==r[j]) ++r[j]; return p[i]=j,i;}int query(int i,int j){ int k=0; if(find(i)==find(j)) while(i^j){ if(d[i]<d[j]) i^=j,j^=i,i^=j; k<f[i]? k=f[i]:0,i=p[i]; } return k;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) p[i]=i; for(;m;--m){ scanf("%d%d%d",&k,&s,&t); s^=l,t^=l; if(k) printf("%d\n", l=query(s,t)); else f[join(s,t)]=++q; }}
bzoj4668: 冷战 并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。