100 但是 MLE
查看原帖
100 但是 MLE
1145602
dongzhenmao楼主2024/8/25 19:42

是否应当开放一点空间(思考) 代码如下,调不出来

#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#include <string.h>
#define lnt long long
#define inf 0x7fffffff
using namespace std;
int xx;char ff,chh;inline int read(){
    xx=ff=0;while(!isdigit(chh)){if(chh=='-'){ff=1;}chh=getchar();}
    while(isdigit(chh)){xx=(xx<<1)+(xx<<3)+chh-'0';chh=getchar();}return ff? -xx: xx;
}
const int N=1e3+2;
struct point{
	int x,y;
	bool operator ==(point a){return a.x==x && a.y==y;}
	bool operator !=(point a){return !(*this==a);}
};
template<typename T>
#define tnt T
struct zy{
	tnt g[N][N];
	tnt &operator [](point a){return g[a.x][a.y];}
};
struct bcj{
	zy<point> g;zy<int> siz;
	bcj(){for(int i=0;i<N;++i){for(int e=0;e<N;++e){g[(point){i,e}]={i,e};}}}
	point find(point a){return g[a]==a? a: g[a]=find(g[a]);}
	void join(point a,point b){g[find(b)]=g[find(a)];}
}s;
zy<int> date;
int n,G;
void dfs(point);
int main(){
	n=read();G=read();
	for(int i=0;i<n;++i){
		for(int e=0;e<n;++e){
			char c=getchar();
			while(c!='0' && c!='1'){c=getchar();}
			date[{i,e}]=c-'0';
		}
	}
	for(int i=0;i<n;++i){
		for(int e=0;e<n;++e){
			if(!s.siz[{i,e}]){
				dfs({i,e});
			}
		}
	}
	while(G--){
		int x=read()-1,y=read()-1;
		point to=s.find({x,y});
		printf("%d\n",s.siz[s.find({x,y})]);
	}
	
    return 0;
}
bool is(point a){return (a.x!=n && a.y!=n && a.x!=-1 && a.y!=-1);}
void dfs(point x){
	s.siz[s.find(x)]++;
	if(s.find(x)!=x){s.siz[x]++;}
	point to={x.x+1,x.y};
	if(is(to) && !s.siz[to] && date[to]+date[x]==1){
		s.join(x,to);
		dfs(to);
	}
	to={x.x-1,x.y};
	if(is(to) && !s.siz[to] && date[to]+date[x]==1){
		s.join(x,to);
		dfs(to);
	}
	to={x.x,x.y-1};
	if(is(to) && !s.siz[to] && date[to]+date[x]==1){
		s.join(x,to);
		dfs(to);
	}
	to={x.x,x.y+1};
	if(is(to) && !s.siz[to] && date[to]+date[x]==1){
		s.join(x,to);
		dfs(to);
	}
}
2024/8/25 19:42
加载中...