【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 0≤vali≤ 220

ぶんせき

ダイレクトエッジは明らかにタイムアウトし、構図の最適化を考慮します.各ウェイト値にポイントを作成し、ウェイト値が到達できる他のウェイト値に長さ0のエッジを接続します.次に、各ブロックはその重み値に長さ0のエッジを接続し、重み値はブロックに長さ1のエッジを接続します.明らかに走り出した最短ルートは等価だ.そうですね.等価です.しかし、到達できる他の重み値にエッジを接続すると、エッジが多すぎます.バイナリの下に1つ少ないエッジを下ろすだけでいいです.辺権は0、1しかないので、最短を走るにはbfsでいいです.注意:ウェイト値0のエッジで接続されたポイントを拡張し、キュー内のdis[]と同じポイントを拡張してから、キュー内の最短ルートの長さが増加することを保証します.

#include 
#include 
#include 

using namespace std;

const int M=1<<20,N=200005,maxn=N+M;

typedef long long LL;

int val[N],tot,dis[maxn],Data[maxn],n,m,h[maxn],e[maxn],nxt[maxn];

bool v[maxn];

char c;

int read()
{
    for (c=getchar();c<'0' || c>'9';c=getchar());
    int x=c-48;
    for (c=getchar();c>='0' && c<='9';c=getchar()) x=x*10+c-48;
    return x;
}

int lowbit(int x)
{
    return x&-x;
}

void add(int x,int y)
{
    e[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
}

void put(int x)
{
    if (!x) return;
    int i,j;
    for (i=x;i;i^=j)
    {
        j=lowbit(i);
        if (!v[x^j])
        {
            Data[++m]=x^j;
            v[x^j]=1;
            dis[x^j]=dis[x];
            put(x^j);
        }
    }
}

int main()
{
    freopen("walk.in","r",stdin); freopen("walk.out","w",stdout);
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        val[i]=read();
        add(val[i],i+M);
    }
    while (m--)
    {
        int x=read(),y=read();
        add(x+M,y+M);
    }
    Data[m=1]=M+1; v[M+1]=1;
    memset(dis,255,sizeof(dis));
    dis[M+1]=0;
    for (int i=1;i<=m;i++)
    {
        int j;
        for (j=i;j<=m && dis[Data[i]]==dis[Data[j]];j++);
        for (int k=i;kint x=Data[k];
            if (x>M)
            {
                if (!v[val[x-M]])
                {
                    Data[++m]=val[x-M];
                    v[Data[m]]=1;
                    dis[Data[m]]=dis[x];
                    put(Data[m]);
                }
            }else put(x);
        }
        for (int k=i;kint x=Data[k];
            for (int i=h[x];i;i=nxt[i]) if (!v[e[i]])
            {
                v[e[i]]=1;
                Data[++m]=e[i];
                dis[e[i]]=dis[x]+1;
            }
        }
        i=j-1;
    }
    for (int i=1;i<=n;i++) printf("%d
",dis[i+M]);
    fclose(stdin); fclose(stdout);
    return 0;
}