@[sbno333](/user/416975) `int merge` 没有 return
by sunkuangzheng @ 2024-03-05 07:51:48
这么卷
by henrytb @ 2024-03-05 10:26:24
@[sunkuangzheng](/user/679936) 一关，已经拿到了分数。
by sbno333 @ 2024-03-05 18:09:39
@[sunkuangzheng](/user/679936) 不 RE 了，但是怎么改都是TLE。（你可以看到我的提交，68分）
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
struct st{
int lson,rson;
int l,r;
int ans;
};
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
void write(int x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
struct node{
st f[5000009];
//map<int,st> f;
int root[1000009];
int bb;
int inn;
inline void pushup(int t){
if(f[t].l^f[t].r){
f[t].ans=f[f[t].lson].ans+f[f[t].rson].ans;
}
}
inline int build(int l,int r){
if(!(l^r)){
//f[++inn].ans=read();
f[++inn].ans=l;
f[inn].l=l,f[inn].r=r;
return inn;
}
int z;
z=++inn;
f[inn].l=l,f[inn].r=r;
int mid;
mid=l+r;
mid>>=1;
f[z].lson=build(l,mid);
f[z].rson=build(mid+1,r);
//pushup(z);
return z;
}
inline int answer(int t,int x){
if(!(f[t].l^1)&!(f[t].r^n)){
root[++bb]=inn+1;
}
if(f[t].l^f[t].r){
f[++inn].l=f[t].l;
f[inn].r=f[t].r;
f[inn].ans=f[t].ans;
return f[t].ans;
}
int mid;
mid=f[t].l+f[t].r;
mid>>=1;
f[++inn].l=f[t].l;
f[inn].r=f[t].r;
if(x<=mid){
f[inn].rson=f[t].rson;
f[inn].lson=inn+1;
return answer(f[t].lson,x);
}else{
f[inn].lson=f[t].lson;
f[inn].rson=inn+1;
return answer(f[t].rson,x);
}
//pushup(z);
}
inline int answ(int t,int x){
if(!(f[t].l^f[t].r)){
return f[t].ans;
}
int mid;
mid=f[t].l+f[t].r;
mid>>=1;
if(x<=mid){
return answ(f[t].lson,x);
}else{
return answ(f[t].rson,x);
}
}
inline void change(int t,int x,int y){
if(!(f[t].l^1)&!(f[t].r^n)){
root[++bb]=inn+1;
}
if(!(f[t].l^f[t].r)){
f[++inn].l=f[t].l;
f[inn].r=f[t].r;
f[inn].ans=y;
return;
}
int mid;
mid=f[t].l+f[t].r;
mid>>=1;
f[++inn].l=f[t].l;
f[inn].r=f[t].r;
if(x<=mid){
f[inn].rson=f[t].rson;
f[inn].lson=inn+1;
change(f[t].lson,x,y);
}else{
f[inn].lson=f[t].lson;
f[inn].rson=inn+1;
change(f[t].rson,x,y);
}
}
int getfa(int u,int x){
int s;
s=answ(root[u],x);
while(x^s){
x=s;
s=answ(root[u],x);
}
return x;
}
void merge(int u,int x,int y){
int s1,s2;
s1=s2=0;
int s;
s=answ(root[u],x);
while(x^s){
x=s;
s=answ(root[u],x);
s1++;
}
s=answ(root[u],y);
while(y^s){
y=s;
s=answ(root[u],y);
s2++;
}
if(s1>s2){
swap(x,y);
}
change(root[u],x,y);
}
}a;
int tim[1000009];
int inn;
int main(){
//freopen("sd.in","r",stdin);
//freopen("sd.out","w",stdout);
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;
//cin>>n>>q;
//cin>>n>>q;
n=read(),q=read();
a.root[0]=a.build(1,n);
int u;
u=0;
for(int i=1;i<=q;i++){
int op;
//cin>>op;
op=read();
if(op==1){
int x,y;
x=read(),y=read();
a.merge(tim[i-1],x,y);
tim[i]=++inn;
}else if(op==2){
int x;
x=read();
tim[i]=tim[x];
}else{
int x,y;
x=read(),y=read();
write((a.getfa(tim[i-1],x)==a.getfa(tim[i-1],y)));
putchar('\n');
tim[i]=tim[i-1];
}
}
return 0;
}
```
by sbno333 @ 2024-03-05 22:24:27