莫名其妙 MLE 求助

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=2000010,R=4000010;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int n,m,a[N][N],s[N][N],r[N][N];
char c[N][N];
vector<pair<int,int>> e[M];
int g[M],cnt,sz[M],fr[M][25],dep[M];
vector<int> f[M];
struct nd{
	int x,y,w;
	bool operator<(const nd &a)const{
		return w>a.w;
	}
}ed[R];
void dfs0(int u,int fa){
	fr[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(int v:f[u]){
		if(v==fa) continue;
		dfs0(v,u);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int j=22;j>=0;j--){
		int u=fr[x][j];
		if(u&&dep[u]>=dep[y]){
			x=u;
		}
	}
	if(x==y) return x;
	for(int j=22;j>=0;j--){
		int u=fr[x][j],v=fr[y][j];
		if(u&&v&&u!=v){
			x=u;
			y=v;
		}
	}
	return fr[x][0];
}
struct ds1{
	int fa[M];
	int getfa(int x){
		if(fa[x]==x) return x;
		return fa[x]=getfa(fa[x]);
	}
	void fadd(int x,int y){
//		cerr<<x<<" "<<y<<"\n";
		f[x].push_back(y);
		f[y].push_back(x);
	}
	void gen_tree(){
		cnt=n*n;
		for(int i=1;i<M;i++){
			fa[i]=i;
		}
		for(int i=1;i<=m;i++){
			int x=ed[i].x,y=ed[i].y,w=ed[i].w;
//			cerr<<x<<" "<<y<<" "<<w<<"-----\n";
			x=getfa(x),y=getfa(y);
//			cerr<<x<<" "<<y<<"**\n";
			if(x!=y){
				cnt++;
				fadd(cnt,x);
				fadd(cnt,y);
				fa[x]=cnt;
				fa[y]=cnt;
				g[cnt]=w;
			}
		}
	}
}t1;
int sqr(int ax,int ay,int bx,int by){
	return s[bx][by]-s[bx][ay-1]-s[ax-1][by]+s[ax-1][ay-1];
}
bool in(int x,int y){
	return 1<=x&&x<=n&&1<=y&&y<=n;
}
bool cks(int x,int y,int k){
	return in(x+k,y+k)&&in(x+k,y-k)&&in(x-k,y+k)&&in(x-k,y-k);
}
void add(int x,int y,int w){
	e[x].push_back({w,y});
	e[y].push_back({w,x});
	ed[++m]={x,y,w};
}
signed main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>(c[i]+1);
		for(int j=1;j<=n;j++){
			if(c[i][j]=='#') s[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			s[i][j]+=s[i][j-1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			s[i][j]+=s[i-1][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(c[i][j]=='#') continue;
			int le=0,ri=n,mid;
			while(le<ri){
				mid=(le+ri+1)>>1;
				if(cks(i,j,mid)&&sqr(i-mid,j-mid,i+mid,j+mid)==0) le=mid;
				else ri=mid-1;
			}
			a[i][j]=2*le+1;
		} 
	}
/*	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<a[i][j]<<" ";
		}
		cerr<<"\n";
	}*/
	int cs=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			r[i][j]=++cs;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int l=0;l<4;l++){
				int tx=i+dx[l],ty=j+dy[l];
				if(!in(tx,ty)) continue;
				int w=min(a[i][j],a[tx][ty]);
				add(r[i][j],r[tx][ty],w);
			}
		}
	}
	sort(ed+1,ed+m+1);
	t1.gen_tree();
	dfs0(cnt,0);
	for(int j=1;j<=22;j++){
		for(int i=1;i<=2*n*n;i++){
			fr[i][j]=fr[fr[i][j-1]][j-1];
		}
	}
/*	for(int j=0;j<=22;j++){
		for(int i=1;i<=2*n*n;i++){
			if(j<=5) cerr<<i<<" "<<j<<" "<<fr[i][j]<<"\n";
		}
	}*/
	int q;
	cin>>q;
	while(q--){
		int ax,ay,bx,by,x,y;
		cin>>ax>>ay>>bx>>by;
		x=r[ax][ay];
		y=r[bx][by];
//		cerr<<x<<" "<<y<<" "<<lca(x,y)<<"\n";
		cout<<g[lca(x,y)]<<"\n";
	}
}