C++14(g++5.4) 解法, 执行用时: 182ms, 内存消耗: 64612K, 提交时间: 2020-06-24 23:26:37
#include <iostream>
#include <cstdio>
using namespace std;
const int N=2*1e5+10,M=N*40;
int n,m,tot,lastans;
int root[N],f[M],dep[M],L[M],R[M];
inline int Build(int l,int r) {
int rt=++tot;
if (l==r) {
f[rt]=l;
return rt;
}
int mid=(l+r)>>1;
L[rt]=Build(l,mid);
R[rt]=Build(mid+1,r);
return rt;
}
inline int Updata(int p,int l,int r,int x,int y) {
int rt=++tot;
L[rt]=L[p];
R[rt]=R[p];
f[rt]=f[p];
dep[rt]=dep[p];
if (l==r) {
f[rt]=y;
return rt;
}
int mid=(l+r)>>1;
if (x<=mid) L[rt]=Updata(L[p],l,mid,x,y);
else R[rt]=Updata(R[p],mid+1,r,x,y);
return rt;
}
inline int Ask(int p,int l,int r,int x) {
if (l==r) return p;
int mid=(l+r)>>1;
if (x<=mid) return Ask(L[p],l,mid,x);
else return Ask(R[p],mid+1,r,x);
}
inline void Add(int p,int l,int r,int x) {
if (l==r) {
dep[p]++;
return;
}
int mid=(l+r)>>1;
if (x<=mid) Add(L[p],l,mid,x);
else Add(R[p],mid+1,r,x);
}
inline int getf(int x,int rt) {
int p=Ask(rt,1,n,x);
if (f[p]==x) return p;
return getf(f[p],rt);
}
const int Mxdt=100000;
inline char gc(){
static char buf[Mxdt],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline char pc(char ch,bool bj){
static char buf[Mxdt],*p1=buf,*p2=buf+Mxdt;
return (bj||(*p1++=ch)&&p1==p2)&&fwrite(p1=buf,1,p1-buf,stdout),0;
}
inline int read()
{
int res=0,bj=0;char ch=gc();
while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=gc();
while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+(ch^48),ch=gc();
return bj?-res:res;
}
inline void print(int x)
{
if(x>9)print(x/10);
pc(x%10^48,false);
}
inline void printnum(int x,char ch)
{
if(x<0)pc('-',false),x=-x;
print(x),pc(ch,false);
}
int main() {
n=read();
m=read();
root[0]=Build(1,n);
for (int i=1;i<=m;i++) {
int op,x,y;
op=read();
x=read();
if (op==1) {
y=read();
root[i]=root[i-1];
int fx=getf(x,root[i-1]);
int fy=getf(y,root[i-1]);
if (f[fx]==f[fy]) continue;
if (dep[fx]>dep[fy]) swap(fx,fy);
root[i]=Updata(root[i-1],1,n,f[fx],f[fy]);
if (dep[fx]==dep[fy]) Add(root[i],1,n,f[fy]);
} else if (op==2) {
root[i]=root[x];
} else {
y=read();
root[i]=root[i-1];
int fx=getf(x,root[i]),fy=getf(y,root[i]);
if (f[fx]==f[fy]) {
pc('1',false);
pc('\n',false);
} else {
pc('0',false);
pc('\n',false);
}
}
}
return pc('♀',true);
}
C++(g++ 7.5.0) 解法, 执行用时: 121ms, 内存消耗: 66204K, 提交时间: 2022-08-09 19:34:44
#include<bits/stdc++.h>
#define il inline
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N=2e5+5;
int n,m,ans,cnt,rt[N];
struct node{
int l,r,d,fa;
}t[N*40];
il int read(){
int x,f=1;char ch;
_(!)ch=='-'?f=-1:f;x=ch^48;
_()x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
il void build(int &x,int l,int r){
x=++cnt;
if(l==r){t[x].d=1;t[x].fa=l;return;}
int mid=(l+r)>>1;
build(t[x].l,l,mid);build(t[x].r,mid+1,r);
}
il int query(int x,int l,int r,int pos){
if(l==r)return x;
int mid=(l+r)>>1;
if(pos<=mid)return query(t[x].l,l,mid,pos);
return query(t[x].r,mid+1,r,pos);
}
il int getfa(int root,int x){
int now=query(root,1,n,x);
if(t[now].fa==x)return now;
return getfa(root,t[now].fa);
}
il void update(int &x,int y,int l,int r,int A,int Fa){
x=++cnt;
if(l==r){t[x].fa=Fa;t[x].d=t[y].d;return;}
t[x].l=t[y].l;t[x].r=t[y].r;
int mid=(l+r)>>1;
if(A<=mid)update(t[x].l,t[y].l,l,mid,A,Fa);
else update(t[x].r,t[y].r,mid+1,r,A,Fa);
}
il void add(int &x,int y,int l,int r,int pos){
x=++cnt;
if(l==r){t[x].d=t[y].d+1;t[x].fa=pos;return;}
int mid=(l+r)>>1;t[x].l=t[y].l;t[x].r=t[y].r;
if(pos<=mid)add(t[x].l,t[y].l,l,mid,pos);
else add(t[x].r,t[y].r,mid+1,r,pos);
}
int main()
{
n=read();m=read();
build(rt[0],1,n);
for(int i=1;i<=m;i++){
rt[i]=rt[i-1];int op=read();
if(op==1){
int a=read()^ans,b=read()^ans;
int x=getfa(rt[i],a),y=getfa(rt[i],b);
if(t[x].fa==t[y].fa)continue;
if(t[x].d>t[y].d)swap(x,y);
update(rt[i],rt[i-1],1,n,t[x].fa,t[y].fa);
if(t[x].d==t[y].d)add(rt[i],rt[i],1,n,t[y].fa);
}
else if(op==2){
int x=read()^ans;rt[i]=rt[x];
}
else{
int a=read()^ans,b=read()^ans;
int x=getfa(rt[i],a),y=getfa(rt[i],b);
if(t[x].fa==t[y].fa)ans=1;else ans=0;
printf("%d\n",ans);
}
}
return 0;
}
C++ 解法, 执行用时: 136ms, 内存消耗: 101412K, 提交时间: 2021-08-12 19:27:17
#include<bits/stdc++.h>
using namespace std;
const int _=2e5+5;
int re(){
int x=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*w;
}
int n,m,now,top,ans;
int a[_],ver[_];
struct tr{
int tot,rt[_],val[_*22],ls[_*22],rs[_*22];
void bu(int&x,int l,int r){
x=++tot;if(l==r){val[x]=a[l];return;}
int mid=(l+r)>>1;bu(ls[x],l,mid);bu(rs[x],mid+1,r);
}
void upd(int&x,int l,int r,int k,int v){
++tot;ls[tot]=ls[x];rs[tot]=rs[x];x=tot;
if(l==r){val[x]=v;return;}int mid=(l+r)>>1;
k<=mid?upd(ls[x],l,mid,k,v):upd(rs[x],mid+1,r,k,v);
}
int q(int x,int l,int r,int k){
if(l==r)return val[x];int mid=(l+r)>>1;
return k<=mid?q(ls[x],l,mid,k):q(rs[x],mid+1,r,k);
}
}fa,sz;
int find(int x){
int f=fa.q(fa.rt[now],1,n,x);
return x==f?x:find(f);
}
void unite(int x,int y){
x=find(x);y=find(y);
if(x==y)return;
int A=sz.q(sz.rt[now],1,n,x),B=sz.q(sz.rt[now],1,n,y);
if(A<B)swap(x,y);++top;
fa.rt[top]=fa.rt[now];
fa.upd(fa.rt[top],1,n,y,x);
sz.rt[top]=sz.rt[now];
sz.upd(sz.rt[top],1,n,x,A+B);
now=top;
}
int main(){
n=re(),m=re();
for(int i=1;i<=n;i++)a[i]=i;
fa.bu(fa.rt[0],1,n);
for(int i=1;i<=n;i++)a[i]=1;
sz.bu(sz.rt[0],1,n);
int op,a,b;
for(int i=1;i<=m;i++){
op=re(),a=re()^ans;
if(op==1){b=re()^ans;unite(a,b);}
if(op==2)now=ver[a];
if(op==3){b=re()^ans;printf("%d\n",ans=(find(a)==find(b)));}
ver[i]=now;
}
return 0;
}
