CodeForces 1419F Rain of Fire

题意

不想写。

题解

场上想了 1h+ 无果，一到场外就口胡出来了，我真是个 sb。

首先注意到如果 \(t\) 满足条件那么 \(t+1\) 也会满足，所以答案具有单调性，可以二分，于是现在只需要考虑对于某个特定的 \(t\) 能否满足。

注意到对于平面上的 \(u,v,w\) 三个点来说，如果 \(u\) 能到 \(v\)，\(v\) 能到 \(w\) 那么 \(u\) 一定能到 \(w\)。

既然这个可达性是可以传递的，那么可以用一个并查集来将相互到的点缩成一个连通块。

如果连通块个数为 \(1\) 那么一定可以，大于 \(4\) 就一定不行，剩下的情况讨论一下。

如果连通块个数为 \(2\)，那么只需要找出两个分属不同连通块的点，然后看看加一个点能不能使得这两个点互相可达即可。

如果连通块个数为 \(3\)，那么只需要找出一条线段和一个点，线段的两个端点和选出来的点分属三个不同的连通块。这个时候注意到加的那个点是已经确定了的，所以直接判断一下即可。

如果连通块个数为 \(4\)，那么只需要找出两条相交的线段，四个端点分属不同的连通块。这个时候新加的那个点就是线段的端点。简单判断一下可达性即可。

本题代码细节比较多，建议配合代码理解。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

const ll MAXN=1e3+51;

struct Tuple{

    ll x,y;

    inline bool operator <(const Tuple &rhs)const

    {

        return this->x==rhs.x?this->y<rhs.y:this->x<rhs.x;

    }

};

map<ll,vector<Tuple>>row,col;

ll n,totr,totc,l,r,mid,res=-1;

ll ffa[MAXN],x[MAXN],y[MAXN],bel[MAXN],rows[MAXN],cols[MAXN];

inline ll read()

{

    register ll num=0,neg=1;

    register char ch=getchar();

    while(!isdigit(ch)&&ch!='-')

    {

        ch=getchar();

    }

    if(ch=='-')

    {

        neg=-1;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        num=(num<<3)+(num<<1)+(ch-'0');

        ch=getchar();

    }

    return num*neg;

}

inline ll find(ll x)

{

    return x==ffa[x]?x:ffa[x]=find(ffa[x]);

}

inline void merge(ll x,ll y)

{

    ll fx=find(x),fy=find(y);

    if(fx!=fy)

    {

        ffa[fy]=fx;

    }

}

inline ll check(ll mid)

{

    ll blk=0,p,q,r,s,lx,rx;

    for(register int i=1;i<=n;i++)

    {

        ffa[i]=i;

    }

    for(register int i=1;i<=n;i++)

    {

        for(register int j=i+1;j<=n;j++)

        {

            if(x[i]==x[j]&&abs(y[i]-y[j])<=mid)

            {

                merge(i,j);

            }

            if(y[i]==y[j]&&abs(x[i]-x[j])<=mid)

            {

                merge(i,j);

            }

        }

    }

    for(register int i=1;i<=n;i++)

    {

        blk+=(find(i)==i);

    }

    if(blk==1)

    {

        return 1;

    }

    if(blk>4)

    {

        return 0;

    }

    for(register int i=1;i<=n;i++)

    {

        bel[i]=ffa[i];

    }

    if(blk==2)

    {

        for(register int i=1;i<=n;i++)

        {

            for(register int j=1;j<=n;j++)

            {

                if(bel[i]==bel[j])

                {

                    continue;

                }

                if(x[i]==x[j]&&abs(y[i]-y[j])<=2*mid)

                {

                    return 1;

                }

                if(y[i]==y[j]&&abs(x[i]-x[j])<=2*mid)

                {

                    return 1;

                }

                if(abs(x[i]-x[j])<=mid&&abs(y[i]-y[j])<=mid)

                {

                    return 1;

                }

            }

        }

        return 0;

    }

    if(blk==3)

    {

        vector<Tuple>v;

        for(register int i=1;i<=totr;i++)

        {

            for(register int j=1;j<row[rows[i]].size();j++)

            {

                p=row[rows[i]][j-1].y,q=row[rows[i]][j].y;

                bel[p]!=bel[q]?v.push_back((Tuple){p,q}):(void)1;

            }

        }

        for(register int i=1;i<=totc;i++)

        {

            for(register int j=1;j<col[cols[i]].size();j++)

            {

                p=col[cols[i]][j-1].y,q=col[cols[i]][j].y;

                bel[p]!=bel[q]?v.push_back((Tuple){p,q}):(void)1;

            }

        }

        for(register int i=0;i<v.size();i++)

        {

            p=v[i].x,q=v[i].y;

            for(register int j=1;j<=n;j++)

            {

                if(bel[p]==bel[j]||bel[q]==bel[j])

                {

                    continue;

                }

                if(x[p]==x[q])

                {

                    lx=min(y[p],y[q]),rx=max(y[p],y[q]);

                    if(y[j]>lx&&y[j]<rx&&abs(x[j]-x[p])<=mid)

                    {

                        if(abs(y[j]-y[p]<=mid)&&abs(y[j]-y[q])<=mid)

                        {

                            return 1;

                        }

                    }

                }

                else

                {

                    lx=min(x[p],x[q]),rx=max(x[p],x[q]);

                    if(x[j]>lx&&x[j]<rx&&abs(y[j]-y[p])<=mid)

                    {

                        if(abs(x[j]-x[p]<=mid)&&abs(x[j]-x[q])<=mid)

                        {

                            return 1;

                        }

                    }

                }

            }

        }

        return 0;

    }

    if(blk==4)

    {

        vector<Tuple>vx,vy;

        for(register int i=1;i<=totr;i++)

        {

            for(register int j=1;j<row[rows[i]].size();j++)

            {

                p=row[rows[i]][j-1].y,q=row[rows[i]][j].y;

                bel[p]!=bel[q]?vx.push_back((Tuple){p,q}):(void)1;

            }

        }

        for(register int i=1;i<=totc;i++)

        {

            for(register int j=1;j<col[cols[i]].size();j++)

            {

                p=col[cols[i]][j-1].y,q=col[cols[i]][j].y;

                bel[p]!=bel[q]?vy.push_back((Tuple){p,q}):(void)1;

            }

        }

        for(register int i=0;i<vx.size();i++)

        {

            for(register int j=0;j<vy.size();j++)

            {

                p=vx[i].x,q=vx[i].y,r=vy[j].x,s=vy[j].y,lx=x[p],rx=y[r];

                if(bel[p]==bel[r]||bel[p]==bel[s])

                {

                    continue;

                }

                if(bel[q]==bel[r]||bel[q]==bel[s])

                {

                    continue;

                }

                if(y[r]<=min(y[p],y[q])||y[r]>=max(y[p],y[q]))

                {

                    continue;

                }

                if(x[p]<=min(x[r],x[s])||x[p]>=max(x[r],x[s]))

                {

                    continue;

                }

                if(abs(rx-y[p])<=mid&&abs(rx-y[q])<=mid)

                {

                    if(abs(lx-x[r])<=mid&&abs(lx-x[s])<=mid)

                    {

                        return 1;

                    }

                }

            }

        }

        return 0;

    }

}

int main()

{

    n=read(),r=2e9;

    for(register int i=1;i<=n;i++)

    {

        rows[++totr]=x[i]=read(),cols[++totc]=y[i]=read();

        row[x[i]].push_back((Tuple){y[i],i});

        col[y[i]].push_back((Tuple){x[i],i});

    }

    sort(rows+1,rows+totr+1),sort(cols+1,cols+totc+1);

    totr=unique(rows+1,rows+totr+1)-rows-1;

    totc=unique(cols+1,cols+totc+1)-cols-1;

    for(register int i=1;i<=totr;i++)

    {

        sort(row[rows[i]].begin(),row[rows[i]].end());

    }

    for(register int i=1;i<=totc;i++)

    {

        sort(col[cols[i]].begin(),col[cols[i]].end());

    }

    while(l<=r)

    {

        mid=(l+r)>>1;

        check(mid)?res=mid,r=mid-1:l=mid+1;

    }

    printf("%d\n",res);

}

巴特西

CodeForces 1419F Rain of Fire

题意

题解

代码

最新文章

热门文章