[Luogu P5068][Ynoi2015]我回来了

题目链接：

Luogu P5068 [Ynoi2015]我回来了

首先这题并不难，只是duliu卡常数罢了，是Ynoi里面比较友好的一道题。

先预处理\(f[i][j]\)表示\(Dist(i,k)\le j\)的点\(k\)集合，那么对每一个点BFS一边

然后求答案的话取个并集就好了。

以上步骤都可以用bitset加速

时间复杂度 \(O(nm+\frac{n^3}{32}+\frac{n\sum a}{32})\)

还有一点，分析复杂度你会发现BFS竟然是这个题复杂度的瓶颈。。

如果你使用前向星存图就会全部TLE，可以用std::vector或者开\(n\)个栈来存图（这题要判重边），这样由于内存连续就可以卡Cache从而AC

全手写了一边，卡了Luogu Rank2，

代码：

//Absoulute LanrTabe
#include <cstdio>
#include <cctype>
#include <cstring>
#define rint register int
typedef unsigned int ui;

#define Getchar (p1==p2&&(p2=(p1=In)+fread(In,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char In[1<<21],*p1=In,*p2=In,Ch;
inline int Getint(rint x=0)
{
    while(!isdigit(Ch=Getchar));
    for(;isdigit(Ch);Ch=Getchar)x=x*10+(Ch^48);
    return x;
}

inline int Min(const int a,const int b){return a<b?a:b;}

const ui Mui=0xffffffff;
int Cnt[1<<16];
struct Bitset
{
    ui a[33];
    inline void Set(){memset(a,0xff,sizeof a);}
    inline void Reset(){memset(a,0,sizeof a);}
    inline void Set(const int p){a[p>>5]|=1u<<(p&0x1f);}
    int Count(rint s=0){for(rint i=0;i<33;++i)s+=Cnt[a[i]&0xffff]+Cnt[a[i]>>16&0xffff];return s;}
    inline void operator|=(const Bitset &o){for(rint i=0;i<33;++i)a[i]|=o.a[i];}
}f[1005][1005],S;

int n,m,q,G[1005][1005],Gs[1005];
int Dis[1005],Q[1005],Qh,Qt,Md[1005];
bool Gv[1005][1005];

int main()
{
    //freopen("in.txt","r",stdin);
    for(rint i=1;i<=0xffff;++i)Cnt[i]=Cnt[i>>1]+(i&1);
    n=Getint(),m=Getint(),q=Getint();
    for(rint x,y;m--;)
    {
        x=Getint(),y=Getint();
        if(!Gv[x][y]&&!Gv[y][x])G[x][++Gs[x]]=y,G[y][++Gs[y]]=x,Gv[x][y]=Gv[y][x]=true;
    }
    for(rint s=1;s<=n;++s)
    {
        memset(Dis,-1,sizeof Dis),Dis[Q[Qh=Qt=1]=s]=0;
        for(rint x,d;Qh<=Qt;)
        {
            d=Dis[x=Q[Qh++]],Md[s]=d,f[s][d].Set(x);
            for(rint i=Gs[x],y;i>=1;--i)if(Dis[y=G[x][i]]==-1)Dis[Q[++Qt]=y]=d+1;
        }
        for(rint i=1;i<=Md[s];++i)f[s][i]|=f[s][i-1];
    }
    for(rint a,x,y;q--;printf("%d\n",S.Count()))
        for(S.Reset(),a=Getint();a--;S|=f[x][Min(y,Md[x])])
            x=Getint(),y=Getint();
    return 0;
}