Codeforces #919 : Div2 F2. Smooth Sailing (Hard Version)

なかなか考察しづらい問題。
https://codeforces.com/contest/1920/problem/F2

問題

H*Wのグリッドが与えられる。
グリッドの各セルは島か海かのいずれかであり、島・海はいずれも連結している。
また、外周部には島となるセルはない。

以下のクエリに答えよ。
海上のセルが1つ指定されるので、隣接セルをたどり島を1周回るようにしたい。

その際、一部のマスは火山マスとなっている。
経路中で火山マスからのマンハッタン距離の最小値を最大化したい。
その値を求めよ。

解法

島の1点から右にレイを伸ばす。
グリッドを1周回るには、このレイを奇数回横断しなければならない。

これを踏まえ、2*H*W要素のUnion-Findを使い、火山から距離d以上で連結可能なセルを求めることを考える。
各クエリにおいて所定の距離以上のセルだけで周回できるかを、並列二分探索で求めよう。

int H,W,Q;
vector<int> D[303030];
string S[303030];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
	void dump(int num=um) { //グループ分けした配列を作る
		int i;
		FOR(i,num) G[i].clear();
		FOR(i,num) G[operator[](i)].push_back(i);
	}
};
UF<606060> uf;
vector<int> L[303030],R[303030];
vector<pair<int,int>> Ds[1303030];
vector<pair<int,int>> target[1303030];
vector<pair<int,int>> ev[1303030];
int ty,tx;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>Q;
	queue<int> PQ;
	FOR(y,H) {
		D[y].resize(W,1<<20);
		L[y].resize(W,-1);
		R[y].resize(W,-1+(1<<19));
		cin>>S[y];
		FOR(x,W) {
			if(S[y][x]=='v') {
				D[y][x]=0;
				PQ.push(y*W+x);
			}
			if(S[y][x]=='#') {
				R[y][x]=-1;
			}

			if(S[y][x]=='#'&&ty==0) {
				ty=y,tx=x;
			}
		}
	}
	
	while(PQ.size()) {
		y=PQ.front()/W;
		x=PQ.front()%W;
		PQ.pop();
		int d[4]={0,1,0,-1};
		FOR(i,4) {
			int ty=y+d[i];
			int tx=x+d[i^1];
			if(ty<0||ty>=H||tx<0||tx>=W) continue;
			if(D[ty][tx]==1<<20) {
				D[ty][tx]=D[y][x]+1;
				PQ.push(ty*W+tx);
			}
		}
	}
	FOR(y,H) FOR(x,W) {
		if(S[y][x]=='#') D[y][x]=-1;
		else Ds[D[y][x]].push_back({y,x});
	}
	
	FOR(i,19) {
		FOR(j,(1<<19)+1) ev[j].clear();
		FOR(y,H) FOR(x,W) if(S[y][x]!='#') ev[(L[y][x]+R[y][x])/2].push_back({y,x});
		
		uf.reinit(2*H*W);
		for(j=(1<<19);j>=0;j--) {
			FORR2(cy,cx,Ds[j]) {
				int d[4]={0,1,0,-1};
				FOR(k,4) {
					int sx=cx+d[k];
					int sy=cy+d[k^1];
					if(sx<0||sx>=W||sy<0||sy>=H) continue;
					if(D[sy][sx]<j) continue;
					int cross=(sx!=cx&&min(sx,cx)<tx&&max(sx,cx)==tx&&sy<ty);
					uf((cy*W+cx)*2+0,(sy*W+sx)*2+(0^cross));
					uf((cy*W+cx)*2+1,(sy*W+sx)*2+(1^cross));
				}
			}
			FORR2(cy,cx,ev[j]) {
				assert(2*j==(L[cy][cx]+R[cy][cx]));
				if(uf[(cy*W+cx)*2+0]==uf[(cy*W+cx)*2+1]) L[cy][cx]=j;
				else R[cy][cx]=j;
			}
		}
	}
	
	
	while(Q--) {
		int sy,sx;
		cin>>sy>>sx;
		cout<<L[sy-1][sx-1]<<endl;
	}
	
	
}

まとめ

周回判定も並列二分探索も思いつかず…。