自动搬运

查看原文

来自洛谷，原作者为

	Frodo 分享快乐，快乐就减半；分享痛苦，痛苦就加倍。

搬运于2025-08-24 23:11:16，当前版本为作者最后更新于2025-03-18 16:01:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

首先我们可以用 BFS 计算出每个点的「黑色恐怖距离」。

接下来考虑询问：每次求两点之间权值最小值的最大值，这让我们想到 Kruskal 重构树的性质：原图中两个点之间的所有简单路径上最小边权的最大值 = Kruskal 重构树上两点之间的 LCA 的权值，只是此处边变成了点。

于是直接建图再建一个类似于 Kruskal 重构树的树即可。

时间复杂度

$\Theta (FMN+Q\log FMN)$。

代码

#include<bits/stdc++.h>
using namespace std;
namespace Fastio{
	#define read Fastio::readuint
	#define write Fastio::writeuint
	#define flush Fastio::clear
	#define SIZE (1<<23)
	#define NUMLEN 12
	#define getchar() (_S==_T&&(_T=(_S=_in)+fread(_in,1,SIZE,stdin),_S==_T)?EOF:*_S++)
	char _in[SIZE],*_S=_in,*_T=_in;
	char _out[SIZE],*_P=_out;
	const char *_end=_out+SIZE;
	inline unsigned int readuint(){
		unsigned int ret=0;char ch=getchar();
		while(ch<'0'||ch>'9'){ch=getchar();}
		while(ch>='0'&&ch<='9'){ret=(ret<<1)+(ret<<3)+(ch^48);ch=getchar();}
		return ret;
	}
	inline void clear(){fwrite(_out,1,_P-_out,stdout);_P=_out;}
	inline void putchar(char ch){*(_P++)=ch;if(_P==_end)clear();}
	inline void outuint(unsigned int x){
		if(x==0){putchar(48);return;}
		unsigned int i=0;
		char st[NUMLEN];
		while(x) st[i++]=48^(x%10),x/=10;
		while(i--) putchar(st[i]);
	}
	inline void writeuint(int x,char ch){outuint(x);putchar(ch);}
}
const int N=200100,M=18;
int n,m,l,tot,q,root,dis[N],stk[N],top=0,fa[N],dep[N],f[M][N],st[M][N];
tuple<int,int,int> place[N];
bool vis[N];
vector<int>e[N];
int ID(int i,int j,int k){return (i*m+j)*l+k;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int u,int v){if(u!=(v=find(v))) e[fa[v]=u].push_back(v);}
int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=M-1;~i;i--) if(dep[f[i][u]]>=dep[v]) u=f[i][u];
	for(int i=M-1;~i;i--) if(f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
	if(u!=v) u=f[0][u];
	return u;
}
int main(){
	#ifdef LOCAL
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	#endif
	n=read(),m=read(),l=read(),q=read(),tot=n*m*l;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) for(int k=0;k<l;k++) place[ID(i,j,k)]={i,j,k};
	for(int i=0;i<tot;i++) dis[i]=-1;
	while(q--){
		int i=read()-1,j=read()-1,k=read()-1;
		dis[stk[top++]=ID(i,j,k)]=0;
	}
	for(int I=0;I<top;I++){
		int u=stk[I],v,i,j,k;tie(i,j,k)=place[u];
		if(i&&!~dis[v=ID(i-1,j,k)]) dis[stk[top++]=v]=dis[u]+1;
		if(j&&!~dis[v=ID(i,j-1,k)]) dis[stk[top++]=v]=dis[u]+1;
		if(k&&!~dis[v=ID(i,j,k-1)]) dis[stk[top++]=v]=dis[u]+1;
		if(i+1-n&&!~dis[v=ID(i+1,j,k)]) dis[stk[top++]=v]=dis[u]+1;
		if(j+1-m&&!~dis[v=ID(i,j+1,k)]) dis[stk[top++]=v]=dis[u]+1;
		if(k+1-l&&!~dis[v=ID(i,j,k+1)]) dis[stk[top++]=v]=dis[u]+1;
	}
	for(int i=0;i<tot;i++) fa[i]=i;
	for(int I=top-1;~I;I--){
		int u=stk[I],v,i,j,k;tie(i,j,k)=place[u];vis[u]=true;
		if(i&&vis[v=ID(i-1,j,k)]) merge(u,v);
		if(j&&vis[v=ID(i,j-1,k)]) merge(u,v);
		if(k&&vis[v=ID(i,j,k-1)]) merge(u,v);
		if(i+1-n&&vis[v=ID(i+1,j,k)]) merge(u,v);
		if(j+1-m&&vis[v=ID(i,j+1,k)]) merge(u,v);
		if(k+1-l&&vis[v=ID(i,j,k+1)]) merge(u,v);
	}
	f[0][stk[0]]=stk[0];
	for(int I=0;I<top;I++){
		int u=stk[I];
		for(int v:e[u]) dep[v]=dep[u]+1,f[0][v]=u;
	}
	for(int j=1;j<M;j++) for(int i=0;i<tot;i++) f[j][i]=f[j-1][f[j-1][i]];
	q=read();
	while(q--){
		int ui=read()-1,uj=read()-1,uk=read()-1;
		int vi=read()-1,vj=read()-1,vk=read()-1;
		write(dis[lca(ID(ui,uj,uk),ID(vi,vj,vk))],10);
	}
	flush();
	return 0;
}