题解：P14422 [JOISC 2014] 水桶 / Water Bottle

· · 题解

整体二分 + 并查集。

赛时思路：

整体二分并查集？

但是我怎么知道两个关键点之间的距离啊？
直接跑是 O(pnm) 的显然过不去啊。
诶诶欸？等会。我是不是可以 p 个点同时 bfs？

ber 哥们，那你牛魔也连不完啊？
不是哥们，我发现了个性质就是：

每个点在方向（某种意义上） 只需要像它一个连边即可。

上述结论实际上想表达的是一些边没用。
这时我们的 dis 数组虽然没有处理完善但是在并查集那已经够用了。

这时我们跑一个多源 bfs 即可，在相交处接受一个边，可以见代码。

整体二分每次类似指针移动地连边跑可撤销并查集就可以了。

复杂度是 O(nm \log^2 (nm))。

#include<bits/stdc++.h>
using namespace std;
const int QAQ=2100,ovo=QAQ*QAQ;
int n,m,p,q;
inline int id(int x,int y) {return x*m+y;}
char wor[QAQ][QAQ];
const int TAT=2e5+19,roxy=5100,inf=2e9;
int x[TAT],y[TAT],dy[QAQ][QAQ],cb[QAQ][QAQ],f[TAT],siz[TAT];
struct xxx {int x,y,bu,id;} ;
bitset<QAQ> vis[QAQ];
queue<xxx> dui;
unordered_map<int,int> dis[TAT];
struct bbb {int u,v;} ;
vector<bbb> ccx[ovo];
void pao()
{
    while(!dui.empty())
    {
        xxx nw=dui.front();dui.pop();
        if(nw.x-1>=1&&wor[nw.x-1][nw.y]!='#')
        {
            if(!vis[nw.x-1][nw.y])
            {
                dui.push({nw.x-1,nw.y,nw.bu+1,nw.id}),vis[nw.x-1][nw.y]=1;
                dy[nw.x-1][nw.y]=nw.id;
                cb[nw.x-1][nw.y]=nw.bu+1;
            }
            else if(dis[nw.id].find(dy[nw.x-1][nw.y])==dis[nw.id].end())
            {
                dis[nw.id][dy[nw.x-1][nw.y]]=dis[dy[nw.x-1][nw.y]][nw.id]=1,
                ccx[nw.bu+cb[nw.x-1][nw.y]].push_back({nw.id,dy[nw.x-1][nw.y]});
            }
        }
        if(nw.x+1<=n&&wor[nw.x+1][nw.y]!='#')
        {
            if(!vis[nw.x+1][nw.y])
            {
                dui.push({nw.x+1,nw.y,nw.bu+1,nw.id}),vis[nw.x+1][nw.y]=1;
                dy[nw.x+1][nw.y]=nw.id;
                cb[nw.x+1][nw.y]=nw.bu+1;

            }
            else if(dis[nw.id].find(dy[nw.x+1][nw.y])==dis[nw.id].end())
            {
                dis[nw.id][dy[nw.x+1][nw.y]]=dis[dy[nw.x+1][nw.y]][nw.id]=1,
                ccx[nw.bu+cb[nw.x+1][nw.y]].push_back({nw.id,dy[nw.x+1][nw.y]});
            }
        }
        if(nw.y-1>=1&&wor[nw.x][nw.y-1]!='#')
        {
            if(!vis[nw.x][nw.y-1])
            {
                dui.push({nw.x,nw.y-1,nw.bu+1,nw.id}),vis[nw.x][nw.y-1]=1;
                dy[nw.x][nw.y-1]=nw.id;
                cb[nw.x][nw.y-1]=nw.bu+1;

            }
            else if(dis[nw.id].find(dy[nw.x][nw.y-1])==dis[nw.id].end())
                dis[nw.id][dy[nw.x][nw.y-1]]=dis[dy[nw.x][nw.y-1]][nw.id]=1,
                ccx[nw.bu+cb[nw.x][nw.y-1]].push_back({nw.id,dy[nw.x][nw.y-1]});
        }
        if(nw.y+1<=m&&wor[nw.x][nw.y+1]!='#')
        {
            if(!vis[nw.x][nw.y+1])
            {
                dui.push({nw.x,nw.y+1,nw.bu+1,nw.id}),vis[nw.x][nw.y+1]=1;
                dy[nw.x][nw.y+1]=nw.id;
                cb[nw.x][nw.y+1]=nw.bu+1;
            }
            else if(dis[nw.id].find(dy[nw.x][nw.y+1])==dis[nw.id].end())
                dis[nw.id][dy[nw.x][nw.y+1]]=dis[dy[nw.x][nw.y+1]][nw.id]=1,
                ccx[nw.bu+cb[nw.x][nw.y+1]].push_back({nw.id,dy[nw.x][nw.y+1]});
        }
    }
}
struct wen {int u,v,id;} d[TAT],o1[TAT],o2[TAT];

int find(int x) {return x==f[x]?x:find(f[x]);}
struct ccc {int x,f,siz;} ;
vector<ccc> che[ovo];

void hebing(int x,int y,int z)
{
    x=find(x),y=find(y);
    if(x==y) return ;
    che[z].push_back({x,f[x],siz[x]});
    che[z].push_back({y,f[y],siz[y]});
    if(siz[x]>siz[y]) swap(x,y);
    f[x]=y;
    siz[y]+=(siz[x]==siz[y]);
}
int ans[TAT],zz=-1;
void chuli(int l,int r,int L,int R)
{
    if(L>R) return ;
    if(l==r)
    {
        for(int i=L;i<=R;i++) ans[d[i].id]=l;
        return ;
    }
    int mid=(l+r)>>1;
    while(zz<mid)
    {
        ++zz;
        for(bbb nw:ccx[zz]) hebing(nw.u,nw.v,zz);
    }
    while(zz>mid)
    {
        if(che[zz].size()>0)
        {
            for(int i=che[zz].size()-1;i>=0;i--)
                f[che[zz][i].x]=che[zz][i].f,siz[che[zz][i].x]=che[zz][i].siz;
            che[zz].clear();
        }
        zz--;
    }

    int cnt1=0,cnt2=0;
    for(int i=L;i<=R;i++)
    {
        if(find(d[i].u)==find(d[i].v)) o1[++cnt1]=d[i];
        else o2[++cnt2]=d[i];
    }
    for(int i=1;i<=cnt1;i++) d[L+i-1]=o1[i];
    for(int i=1;i<=cnt2;i++) d[L+cnt1+i-1]=o2[i];

    chuli(l,mid,L,L+cnt1-1),chuli(mid+1,r,L+cnt1,R);
}

signed main()
{
    freopen("dydx.in","r",stdin);
    freopen("dydx.out","w",stdout);

    scanf("%d%d%d%d",&n,&m,&p,&q);
    for(int i=1;i<=n;i++) scanf("%s",wor[i]+1);
    for(int i=1;i<=p;i++)
        scanf("%d%d",&x[i],&y[i]),dui.push({x[i],y[i],0,i}),
        vis[x[i]][y[i]]=1,wor[x[i]][y[i]]='F',dy[x[i]][y[i]]=i,dis[i][i]=1;

    pao();

    for(int i=1;i<=p;i++) f[i]=i,siz[i]=1;

    for(int i=1;i<=q;i++) scanf("%d%d",&d[i].u,&d[i].v),d[i].id=i;

    int jx=n*m+1;
    chuli(0,jx,1,q);

    for(int i=1;i<=q;i++)
    {
        if(ans[i]==jx) printf("-1\n");
        else printf("%d\n",ans[i]);
    }

    return 0;
}