JZOJ4858. 【GDOI 2017シミュレーション11.4】Walk

タイトルの説明

ビット町には全部でnブロックあり、番号は1からnの順で、それらの間にはいくつかの一方向道路が接続されています.ビット町の交通システムは非常に特色があり、m本の一方向道路のほか、各ブロックにはvaliをコードするコードがあり、異なるブロックは同じコードを持っている可能性があります.val_の場合i and val_j = val_j,すなわちval_iバイナリの下でval_とj演算とval_に等しいj,iからjへの一方向道路も存在する.Byteasarは現在1番街に位置しており、これらの道路を通って各街に着くのに少なくともどのくらいの時間がかかるか知りたいと思っています.ビット町は交通が発達しているので、道ごとに1単位しかかからないと思います.n<=200000,m<=300000,val_i<= 220

ぶんせき

まず,辺権は1しかないので,直接bfsは最短ではないことが分かった.追加パスはどのように処理しますか?暴力のエッジはn 2であるが,点iの最短ルートが処理されたと仮定すると,処理されていないすべてのand条件を満たす点jが処理されることが分かった.ではand条件を満たす点は,バイナリの下でa[j]がa[i]であることを満たすことであり,いくつかの1を削除した結果である.同時に,同じa[j]処理で1回で十分であることに気づき,a[j]が何度も処理されるのを避けるにはどうすればよいのだろうか.仮想点を構築し、n+1~n+max(val_i)と番号付けし、真実点の重み値がある値xの場合、その最短ルートがどれだけであるかを示す.では、私たちはこれらの点を図の中に入れて、1つの辺を歩くたびにバイナリの下の1を削除することに相当して、一緒に走ればいいです.強制的に本気で仮想点に入るには1の費用がかかります.外に出るには使いません.いくつかの細部がありますが、虚点が優先的に走っています.辺権は0ですから.また、辺を全部建てるとスペースが爆発します.実は仮想点に対してエッジを保存する必要はありません.1を削除するとどの点になるか知っているので、エッジを保存する必要はありません.

コード#コード#

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define fo(i,j,k) for(i=j;i<=k;i++)
const int N=200005,M=300005,er=1048576;
int b[M*4],next[M*4],first[N+er],tt;
int dis[N+er],n,m,x,y,a[N],i,j,k,l,dur,p,d[N+er],e[N+er],q1,q2,p1,p2,z,t;
void cr(int x,int y)
{
    tt++;
    b[tt]=y;
    next[tt]=first[x];
    first[x]=tt;
}
void bfs()
{
    fo(i,1,n+er) dis[i]=-1;
    dis[1]=0;
    d[1]=1;
    q1=0;
    q2=1;
    while (q1<q2)
    {
        x=d[++q1];
        for(p=first[x];p;p=next[p])
            if (dis[b[p]]==-1)
            {
                dis[b[p]]=dis[x]+1;
                d[++q2]=b[p];
            }
        if (dis[a[x]+n]==-1)
        {
            dis[a[x]+n]=dis[x]+1;
            e[1]=a[x]+n;
            p1=0;
            p2=1;
            while (p1<p2)
            {
                z=y=e[++p1];
                z-=n;
                for(p=first[y];p;p=next[p])
                if (dis[b[p]]==-1)
                {
                    dis[b[p]]=dis[x]+1;
                    d[++q2]=b[p];
                }
                while (z)
                {
                    t=y-((z)&(-z));
                    if (t==n) break;
                    if (dis[t]==-1)
                    {
                        dis[t]=dis[x]+1;
                        e[++p2]=t;
                    }
                    z-=z&(-z);
                }
            }
        }
    }
}
int main()
{
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,1,n) 
    {
        scanf("%d",a+i);
        cr(a[i]+n,i);
    }
    fo(i,1,m)
    {
        scanf("%d%d",&x,&y);
        cr(x,y);
    }
    bfs();
    fo(i,1,n) 
    {
        printf("%d
",dis[i]);
    }
}