2024-10-21-solution-cf1920f2

大牛逼题目。

牛逼的点在于这个如何判定环绕了岛屿一圈。题解给出了这样一种方式：考虑任意一个岛屿往下垂直的一条射线。如果你的路径从 $(x,y)$ 经过了这个射线奇数次并回到了 $(x,y)$ 那么你就一定包围了这个岛屿。

所以我们直接拆点，连边，边权为 $u,v$ 和最近岛屿的距离的最小值，然后相当于一条最大边权最小的路径。这个直接 kruskal 重构树就做完了。

太牛逼了。代码写得一坨屎。

// Problem: Smooth Sailing (Hard Version)
// URL: https://www.luogu.com.cn/problem/CF1920F2
// Writer: WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 1e6 + 10;

int n, m, q;
vector <char> a[MAX];
vector <int> dis[MAX];
const int nxt[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
inline int To(int x, int y){
	return (x - 1) * m + y;
}

struct node{
	int u, v, w;
}; node g[MAX * 5];


bool cmp(node x, node y){
	return x.w > y.w;
}

int psz;
int fa[MAX * 4];
int val[MAX * 4];

int find(int x){
	if(fa[x] == x)	return x;
	return fa[x] = find(fa[x]);
}

vector <int> g2[MAX * 10];

int fat[MAX * 4], siz[MAX * 4], son[MAX * 4];
int dep[MAX * 4];
void dfs(int u){
	siz[u] = 1;
	for(int v : g2[u]){
		fat[v] = u, dep[v] = dep[u] + 1;
		dfs(v);
		siz[u] += siz[v];
		if(siz[son[u]] < siz[v])	son[u] = v;
	}
}

int top[MAX];

void dfs2(int u, int topu){
	top[u] = topu;
	if(son[u])	dfs2(son[u], topu);
	for(int v : g2[u]){
		if(v != son[u])	dfs2(v, v);
	}
}

int lca(int u, int v){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]])	swap(u, v);
		u = fat[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}

void solve(){
	n = read(), m = read(), q = read();
	queue <pair <int, int>> que;
	
	pair <int, int> loww = make_pair(0, 0);

	for(int i = 1; i <= n; i++){
		a[i].pb('?');
		dis[i].pb(0);
		for(int j = 1; j <= m; j++){
			char ch;
			cin >> ch;
			a[i].pb(ch);
			if(ch == 'v'){
				dis[i].pb(0);
				que.push(make_pair(i, j));
			}else{
				dis[i].pb(inf);
			}
			if(ch == '#'){
				loww = max(loww, make_pair(i, j));
			}
		}
	}
	while(!que.empty()){
		int x = que.front().first, y = que.front().second;
		que.pop();
		for(int i = 0; i < 4; i++){
			int dx = x + nxt[i][0], dy = y + nxt[i][1];
			if(dx > n or dy > m or !dx or !dy)	continue;
			if(dis[dx][dy] > dis[x][y] + 1){
				dis[dx][dy] = dis[x][y] + 1;
				que.push(make_pair(dx, dy));
			}
		}
	}
	// write(loww.first), put(), write(loww.second), endl;
	int m2 = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a[i][j] == '#')	continue;
			for(int k = 0; k < 2; k++){
				int dx = i + nxt[k][0], dy = j + nxt[k][1];
				if(dx > n or dy > m or !dx or !dy or a[dx][dy] == '#')	continue;
				g[++m2].u = To(i, j);
				g[m2].v = To(dx, dy);
				g[m2].w = min(dis[i][j], dis[dx][dy]);
				g[++m2].u = n * m + To(i, j);
				g[m2].v = n * m + To(dx, dy);
				g[m2].w = min(dis[i][j], dis[dx][dy]);
			}
			if(j == loww.second and i >= loww.first){
				for(int k = 2; k < 4; k++){
					int dx = i + nxt[k][0], dy = j + nxt[k][1];
					if(dx > n or dy > m or !dx or !dy or a[dx][dy] == '#')	continue;
					if(k == 2){
						g[++m2].u = To(i, j);
						g[m2].v = n * m + To(dx, dy);
						g[m2].w = min(dis[i][j], dis[dx][dy]);
						g[++m2].u = n * m + To(i, j);
						g[m2].v = To(dx, dy);
						g[m2].w = min(dis[i][j], dis[dx][dy]);
					}else{
						g[++m2].u = To(i, j);
						g[m2].v = To(dx, dy);
						g[m2].w = min(dis[i][j], dis[dx][dy]);
						g[++m2].u = n * m + To(i, j);
						g[m2].v = n * m + To(dx, dy);
						g[m2].w = min(dis[i][j], dis[dx][dy]);
					}
				}
			}else if(j == loww.second + 1 and i >= loww.first){
				for(int k = 2; k < 4; k++){
					int dx = i + nxt[k][0], dy = j + nxt[k][1];
					if(dx > n or dy > m or !dx or !dy or a[dx][dy] == '#')	continue;
					if(k == 3){
						g[++m2].u = To(i, j);
						g[m2].v = n * m + To(dx, dy);
						g[m2].w = min(dis[i][j], dis[dx][dy]);
						g[++m2].u = n * m + To(i, j);
						g[m2].v = To(dx, dy);
						g[m2].w = min(dis[i][j], dis[dx][dy]);
					}else{
						g[++m2].u = To(i, j);
						g[m2].v = To(dx, dy);
						g[m2].w = min(dis[i][j], dis[dx][dy]);
						g[++m2].u = n * m + To(i, j);
						g[m2].v = n * m + To(dx, dy);
						g[m2].w = min(dis[i][j], dis[dx][dy]);
					}
				}
			}else{
				for(int k = 2; k < 4; k++){
					int dx = i + nxt[k][0], dy = j + nxt[k][1];
					if(dx > n or dy > m or !dx or !dy or a[dx][dy] == '#')	continue;
					g[++m2].u = To(i, j);
					g[m2].v = To(dx, dy);
					g[m2].w = min(dis[i][j], dis[dx][dy]);
					g[++m2].u = n * m + To(i, j);
					g[m2].v = n * m + To(dx, dy);
					g[m2].w = min(dis[i][j], dis[dx][dy]);
				}
			}
		}
	}
	sort(g + 1, g + m2 + 1, cmp);
	for(int i = 1; i <= n * m * 2; i++)	fa[i] = i;
	psz = n * m * 2;
	for(int i = 1; i <= m2; i++){
		if(find(g[i].u) == find(g[i].v))	continue;
		g2[++psz].pb(find(g[i].u));	
		g2[psz].pb(find(g[i].v));	
		fa[find(g[i].u)] = fa[find(g[i].v)] = psz;
		fa[psz] = psz;
		val[psz] = g[i].w;
	}
	int rt = find(1);
	dfs(rt);
	dfs2(rt, rt);
	while(q--){
		int x = read(), y = read();
		int ans = lca(To(x, y), To(x, y) + n * m);
		write(val[ans]), endl;
	}
}

signed main(){
	int t = 1;
	while(t--)	solve();
	return 0;
}