P11907 solution
Frodo
·
·
题解
思路
首先我们可以用 BFS 计算出每个点的「黑色恐怖距离」。
接下来考虑询问：每次求两点之间权值最小值的最大值，这让我们想到 Kruskal 重构树的性质：原图中两个点之间的所有简单路径上最小边权的最大值 = Kruskal 重构树上两点之间的 LCA 的权值，只是此处边变成了点。
于是直接建图再建一个类似于 Kruskal 重构树的树即可。
时间复杂度
## 代码
```cpp
#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;
}
```