AtCoder AGC #015 : C - Nuske vs Phantom Thnook

ダメダメでした。
http://agc015.contest.atcoder.jp/tasks/agc015_c

問題

N*Mのグリッド中、いくつかのマスは青く塗られている。
青マスは森を成している。

Q個のクエリが与えられる。
各クエリはグリッド中の矩形範囲を示す。
その範囲内の青マスの連結成分の数を答えよ。

解法

自分はO(HW+Q(H+W))で3sかかる解法で解いた。
各連結成分において、1マスを根とし、そこからDFSで隣接マスをたどり根からの距離を求めていこう。

各クエリに対し、以下の条件で連結成分が増える。

• 根となるマスを含む
• 外部から内側に入ってくる(内側側のマスの方が根までの距離が遠い)

よって累積和の要領で根となるマスの数を求め、あとは周辺部で矩形の境界をまたぐ連結成分の数を求めればよい。

Editorialの通り、O(HW+Q)で済む解法もある。
森の連結成分数は頂点数-辺の数なので、矩形の範囲における頂点数・辺の数を累積和で数え上げればよい。

int H,W,Q;
string S[2020];
int X1[202020],Y1[202020],X2[202020],Y2[202020];
int ret[202020];

int st[2020][2020];
int dep[2020][2020];
int SS[2020][2020];
int vis[2020][2020];

void dfs(int cy,int cx,int d) {
	// left
	int ty,tx;
	vis[cy][cx]=1;
	dep[cy][cx]=d;
	ty=cy,tx=cx-1;
	if(tx>=0 && S[ty][tx]=='1' && vis[ty][tx]==0) dfs(ty,tx,d+1);
	ty=cy,tx=cx+1;
	if(tx<W && S[ty][tx]=='1' && vis[ty][tx]==0) dfs(ty,tx,d+1);
	ty=cy-1,tx=cx;
	if(ty>=0 && S[ty][tx]=='1' && vis[ty][tx]==0) dfs(ty,tx,d+1);
	ty=cy+1,tx=cx;
	if(ty<H && S[ty][tx]=='1' && vis[ty][tx]==0) dfs(ty,tx,d+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>Q;
	FOR(y,H) cin>>S[y];
	
	FOR(i,Q) {
		cin>>Y1[i]>>X1[i]>>Y2[i]>>X2[i];
		X1[i]--;
		Y1[i]--;
		X2[i]--;
		Y2[i]--;
		
	}
	
	FOR(y,H) FOR(x,W) if(S[y][x]=='1' && vis[y][x]==0) {
		vis[y][x]=1;
		st[y][x]++;
		dfs(y,x,2);
	}
	FOR(y,H+1) FOR(x,W+1) SS[y+1][x+1]=SS[y+1][x]+SS[y][x+1]+st[y][x]-SS[y][x];
	
	
	FOR(i,Q) {
		r=SS[Y2[i]+1][X2[i]+1]+SS[Y1[i]][X1[i]]-SS[Y2[i]+1][X1[i]]-SS[Y1[i]][X2[i]+1];
		for(y=Y1[i];y<=Y2[i];y++) {
			if(X1[i]>0 && dep[y][X1[i]]==dep[y][X1[i]-1]+1) r++;
			if(X2[i]<W && dep[y][X2[i]]==dep[y][X2[i]+1]+1) r++;
		}
		for(x=X1[i];x<=X2[i];x++) {
			if(Y1[i]>0 && dep[Y1[i]][x]==dep[Y1[i]-1][x]+1) r++;
			if(Y2[i]<H && dep[Y2[i]][x]==dep[Y2[i]+1][x]+1) r++;
		}
		
		_P("%d\n",r);
	}
}

まとめ

TL 4sということは、O(HW+Q(H+W))も許容すること前提だったのかな。