C++(g++ 7.5.0) 解法, 执行用时: 335ms, 内存消耗: 126136K, 提交时间: 2022-08-03 20:08:00

#include<cstdio>
#include<bitset>
int read()
{
	int a=0;char c;
	while((c=getchar())<'0');
	while(c>='0')a=a*10+(c^48),c=getchar();
	return a;
}
int n,m;std::bitset<1000>r[1000][1000],e[1000];
void bfs(int s)
{
	r[s][0].set(s);
	std::bitset<1000>now,next=e[s];now.set(s),next.set(s);
	for(int i=1;i<n;i++)
	{
		auto t=now^next;r[s][i]=now=next;
		for(int v=t._Find_first();v<n;v=t._Find_next(v))next|=e[v];
		if(r[s][i]==r[s][i-1])for(i++;i<n;i++)r[s][i]=r[s][i-1];
	}
}
int main()
{
	n=read(),m=read();int q=read(),u,v,a;
	while(m--)u=read()-1,v=read()-1,e[u].set(v),e[v].set(u);
	for(int i=0;i<n;i++)bfs(i);
	while(q--)
	{
		std::bitset<1000>ans;a=read();
		while(a--)u=read()-1,v=read(),ans|=r[u][std::min(n-1,v)];
		printf("%d\n",ans.count());
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1027ms, 内存消耗: 128680K, 提交时间: 2020-05-05 13:47:20

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int x,h;
}Q[1005];
int i,j,a,n,m,q;
bitset<1005>T[1005][1005];
vector<int>R[1005];
void BFS(int sx)
{
	int i,j,x,h,r=1,f=0;
	bool V[1005]={0};
	Q[0].x=sx,Q[0].h=0,V[sx]=1;
	while(r!=f)
	{
		x=Q[f].x,h=Q[f++].h;
		T[sx][h][x]=1;
		for(i=0;i<R[x].size();i++)
		{
			j=R[x][i];
			if(!V[j])V[j]=1,Q[r].x=j,Q[r++].h=h+1;
		}
	}
	for(i=1;i<=n-1;i++)T[sx][i]|=T[sx][i-1];
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	while(m--)
	{
		scanf("%d%d",&i,&j);
		R[i].push_back(j),R[j].push_back(i);
	}
	for(i=1;i<=n;i++)BFS(i);
	while(q--)
	{
		scanf("%d",&a);
		bitset<1005>ans;
		while(a--)
		{
			scanf("%d%d",&i,&j),j=min(j,n-1);
			ans|=T[i][j];
		}
		printf("%d\n",ans.count());
	}
	return 0;
}