how d
查看原帖
how d
1020581
The_outcast_person楼主2024/9/7 21:47

可以用并查集的路径压缩写法吗?

如果可以,求问这么写有什么问题:

#include<bits/stdc++.h>
#define int long long
#define il inline
#define pii pair<int,int>
#define mk make_pair
#define mod 998244353
using namespace std;
il int rd(){
    int jya=0,tl=1;char jyt=getchar();
    while(!isdigit(jyt)){if(jyt=='-')tl=-1;jyt=getchar();}
    while(isdigit(jyt)){jya=(jya<<1)+(jya<<3)+(jyt-'0');jyt=getchar();}
    return jya*tl;
}
il void wr(int jjy){
    if(jjy<0)putchar('-'),jjy=-jjy;
    if(jjy>9)wr(jjy/10);
    putchar(jjy%10+48);
}
const int JYAAKIOI=1145141919810;
struct node{
	int up,down,left,right,now;
};
int n,m,q,r,c,ans;
vector<node>a[400086];
il int dfsup(int x,int y){
	if(x<=1)return 1;
	if(a[x][y].now==1){
		a[x][y].now=0;
		a[x][y].up=max(0ll,x-1);
		return a[x][y].up;
	}
	a[x][y].up=dfsup(a[x][y].up,y);
}
il int dfsdown(int x,int y){
	//cout<<x<<" "<<y<<endl;
	if(x>=n)return n;
	if(a[x][y].now==1){
		a[x][y].now=0;
		a[x][y].down=min(n,x+1);
		return a[x][y].down;
	}
	a[x][y].down=dfsdown(a[x][y].down,y);
}
il int dfsleft(int x,int y){
	if(a[x][y].now==1||y<=1){
		a[x][y].now=0;
		a[x][y].left=max(0ll,y-1);
		return a[x][y].left;
	}
	a[x][y].left=dfsleft(x,a[x][y].left);
}
il int dfsright(int x,int y){
	if(a[x][y].now==1||y>=m){
		a[x][y].now=0;
		a[x][y].right=max(m,y+1);
		return a[x][y].right;
	}
	a[x][y].right=dfsright(x,a[x][y].right);
}
signed main(){
	n=rd();m=rd();q=rd();
	for(int i=1;i<=n;++i){
		a[i].push_back({0,0,0,0,1});
		for(int j=1;j<=m;++j){
			a[i].push_back(node{i,i,j,j,1});
			/*a[i][j].up=a[i][j].down=i;
			a[i][j].left=a[i][j].right=j;
			a[i][j].now=1;*/
		}
	}
	while(q--){
		r=rd();c=rd();
		if(a[r][c].now){
			a[r][c].now=0;
			a[r][c].up=max(0ll,r-1);
			a[r][c].down=min(n,r+1);
			a[r][c].left=max(0ll,c-1);
			a[r][c].right=min(m,c+1);
			cout<<a[r][c].up<<endl<<a[r][c].down<<endl<<a[r][c].left<<endl<<a[r][c].right<<endl;
		}
		else {
			dfsup(r,c);
			dfsdown(r,c);
			dfsleft(r,c);
			dfsright(r,c);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(a[i][j].now)++ans;
		}
	}
	wr(ans);
	return 0;
}
2024/9/7 21:47
加载中...