【LOJ2838】「JOISC 2018 Day 3」比太郎的聚会（设阈值预处理/分块）

点此看题面

大致题意： 给你一张\(DAG\)，多组询问，每次问你在起点不为某些点的前提下，到达给定终点的最大距离是多少。

设阈值

由于限制点数总和与\(n\)同阶，因此容易想到去设阈值。

对于限制点数少于\(\sqrt n\)的询问，首先我们可以\(O(n\sqrt n)\)预处理出对于每个点到其距离前\(\sqrt n\)大的点及其距离。

关于这个，可以通过在\(DAG\)上归并转移处理出来。

然后询问时只要\(O(\sqrt n)\)对于给定终点找到第一个非限制点即可。

对于限制点数大于等于\(\sqrt n\)的询问，我们直接\(O(n)\)暴力。

由于这种询问个数不超过\(\sqrt n\)个，因此时间复杂度也是\(O(n\sqrt n)\)的。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 100000

#define M 200000

#define SN 400

#define Gmax(x,y) (x<(y)&&(x=(y)))

#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)

#define add_(x,y) (e_[++ee_].nxt=lnk_[x],e_[lnk_[x]=ee_].to=y)

using namespace std;

int n,m,sn,fg,ee,ee_,s[N+5],lnk[N+5],lnk_[N+5];struct edge {int to,nxt;}e[M+5],e_[M+5];

class FastIO

{

	private:

		#define FS 100000

		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

		#define pc(c) (C==E&&(clear(),0),*C++=c)

		#define tn (x<<3)+(x<<1)

		#define D isdigit(c=tc())

		int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];

	public:

		I FastIO() {A=B=FI,C=FO,E=FO+FS;}

		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}

		Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}

		Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}

		Tp I void writeln(Con Ty& x) {write(x),pc('\n');}

		I void writeNA() {pc('-'),pc('1'),pc('\n');}

		I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}

		#undef D

}F;

class ListDper//预处理

{

	private:

		int f[N+5][SN+5],g[N+5][SN+5],f_[SN+5],g_[SN+5],used[N+5];

	public:

		I void Init()//预处理

		{

			RI i,j,w,k,px,py,pt,ti=0;for(i=1;i<=n;++i) f[i][1]=0,g[i][1]=i;//初始化

			for(i=1;i<=n;++i) for(j=lnk[i];j;j=e[j].nxt)//枚举点转移

			{

				#define Push1 (f_[pt]=f[i][px]+1,used[g_[pt++]=g[i][px++]]=ti)

				#define Push2 (f_[pt]=f[k][py],used[g_[pt++]=g[k][py++]]=ti)

				++ti,k=e[j].to,px=py=pt=1;W(g[i][px]&&g[k][py]&&pt<=sn)//归并

				{

					if(used[g[i][px]]==ti) {++px;continue;}//每个点只考虑一次，这里用了时间戳

					if(used[g[k][py]]==ti) {++py;continue;}//同上

					f[i][px]+1>=f[k][py]?Push1:Push2;//注意转移时距离会加1

				}

				W(g[i][px]&&pt<=sn) used[g[i][px]]^ti?Push1:++px;//处理剩余点

				W(g[k][py]&&pt<=sn) used[g[k][py]]^ti?Push2:++py;//同上

				for(w=1;w^pt;++w) f[k][w]=f_[w],g[k][w]=g_[w];//更新数组

			}

		}

		I void Solve(CI x)//求答案

		{

			RI p=1;W(g[x][p]&&s[g[x][p]]==fg) ++p;//扫一遍求答案

			g[x][p]?F.writeln(f[x][p]):F.writeNA();//输出答案

		}

}D;

class BruteForceSolver//暴力

{

	private:

		int dis[N+5];

	public:

		I void Solve(CI x)

		{

			RI i,j,ans=-1;for(i=1;i^x;++i) dis[i]=-1e9;dis[x]=0;//初始化赋值

			for(i=x;i;--i) for(s[i]^fg&&Gmax(ans,dis[i]),j=lnk_[i];j;j=e_[j].nxt) Gmax(dis[e_[j].to],dis[i]+1);//暴力

			~ans?F.writeln(ans):F.writeNA();//输出答案

		}

}B;

int main()

{

	RI Qtot,i,x,y,z;for(F.read(n,m,Qtot),sn=sqrt(n),i=1;i<=m;++i) F.read(x,y),add(x,y),add_(y,x);//读入+建边

	D.Init();W(Qtot--) {for(F.read(x,y),++fg,i=1;i<=y;++i) F.read(z),s[z]=fg;y<sn?D.Solve(x):B.Solve(x);}//处理询问

	return F.clear(),0;

}

巴特西

【LOJ2838】「JOISC 2018 Day 3」比太郎的聚会（设阈值预处理/分块）

设阈值

代码

最新文章

热门文章