AT_abc236_g

来点另类思路！

首先考虑暴力地做：发现 $L$ 非常大，于是大概率是要矩阵快速幂，求出最后的邻接矩阵的。如果对暴力处理出所有 $T$ 次操作后的最终矩阵，复杂度为 $O(Tn^2\log L)=O(n^4\log L)$。（其实一开始想到了题解区中的 $O(\frac{n^4\log L}{\omega})$ 做法但是我不觉得能过）

但是你发现一个问题：每次只改变一条边，我们会做很多冗余计算。于是考虑把矩阵乘法计算过程列出来，一开始全是 $0$，后面在某一时刻，某些位置可能会变成 $1$，变成 $1$ 的位置后面也不会变成 $0$，于是可以不用管它了。

于是类似 bfs，我们每次拿出一个新变成 $1$ 的位置，看它会影响其他哪些位置也变成 $1$。类似矩阵乘法，在 $A\times B=C$ 中，如果 $A_{i,k}$ 变化，我们就枚举一个 $j$，看 $B_{k,j}$ 是否为 $1$，如果 $C_{i,j}$ 此时为 $0$ 就改为 $1$ 并 push 进 bfs 的队列中。对矩阵乘法过程中每次运算这么操作即可。

时间复杂度 $O(n^3\log L)$。但是你发现时间复杂度瓶颈在枚举上述 $j$，而矩阵中元素改变的次数只有 $O(n^2\log L)$ 次。而（如果我没想错的话）找能改变的位置显然是一个能用 bitset 维护的操作，使用一些 _Find_next 相关即可。再优化一下判断每个点此时是否可达，时间复杂度就降到了 $O(\frac{n^3\log L}{\omega})$。甚至可以直接把 bitset 换成一个 int128，将理论复杂度变为 $O(n^2\log L)$ 然后成功爆标！

但是由于作者比较懒所以还没有实现这个做法，如果你实现了/证伪了这个做法请敲打一下我（

code：

int n,m,k,cur=-1,lim,ans[N],c[M];
int a[M][N][N],b[M][N][N];
vector<pii> g[M];
struct node{
	int p,x,y;
	node(int _p,int _x,int _y):p(_p),x(_x),y(_y){}
};
void upd(int u,int v){
	queue<node> q;
	rep(i,0,lim){
		g[i].clear();
	}
	a[0][u][v]=1;
	q.emplace(0,u,v);
	while(q.size()){
		auto [p,x,y]=q.front();
		q.pop();
		g[p].eb(x,y);
		if(p==lim){
			continue;
		}
		rep(i,1,n){
			if(a[p][y][i]&&!a[p+1][x][i]){
				a[p+1][x][i]=1;
				q.emplace(p+1,x,i);
			}
		}
		rep(i,1,n){
			if(a[p][i][x]&&!a[p+1][i][y]){
				a[p+1][i][y]=1;
				q.emplace(p+1,i,y);
			}
		}
	}
	for(auto [x,y]:g[lim]){
		b[0][x][y]=1;
		q.emplace(0,x,y);
	}
	rep(j,1,cur){
		while(q.size()&&q.front().p==j-1){
			auto [p,x,y]=q.front();
			q.pop();
			rep(i,1,n){
				if(a[c[j]][y][i]&&!b[j][x][i]){
					b[j][x][i]=1;
					q.emplace(j,x,i);
				}
			}
		}
		for(auto [x,y]:g[c[j]]){
			rep(i,1,n){
				if(b[j-1][i][x]&&!b[j][i][y]){
					b[j][i][y]=1;
					q.emplace(j,i,y);
				}
			}
		}
	}
}
void Yorushika(){
	read(n,m,k),lim=__lg(k);
	int tmp=k;
	drep(i,lim,0){
		if(tmp>=(1<<i)){
			c[++cur]=i;
			tmp-=1<<i;
		}
	}
	mems(ans,0x3f);
	rep(t,1,m){
		int u,v;read(u,v);
		upd(u,v);
		rep(i,1,n){
			if(b[cur][1][i]){
				ans[i]=min(ans[i],t);
			}
		}
	}
	rep(i,1,n){
		printf("%d ",ans[i]>1e9?-1:ans[i]);
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

upd：喜报，鸽子写完了。现在在最优解上遥遥领先，耗时是第二的 $\frac{1}{3}$ 左右。

code：

int n,m,k,cur=-1,lim,ans[N],c[M];
int a[M][N][N],b[M][N][N];
bitset<N> f[M][2][N],g[M][2][N];
vector<pii> vec[M];
struct node{
	int p,x,y;
	node(int _p,int _x,int _y):p(_p),x(_x),y(_y){}
};
void upd(int u,int v){
	queue<node> q;
	rep(i,0,lim){
		vec[i].clear();
	}
	bitset<N> tmp,all;
	all.set();
	a[0][u][v]=1;
	f[0][0][u][v]=f[0][1][v][u]=1;
	q.emplace(0,u,v);
	while(q.size()){
		auto [p,x,y]=q.front();
		q.pop();
		vec[p].eb(x,y);
		if(p==lim){
			continue;
		}
		tmp=f[p][0][y]&(f[p+1][0][x]^all);
		for(int i=tmp._Find_first();i<=n;i=tmp._Find_next(i)){
			a[p+1][x][i]=1;
			f[p+1][0][x][i]=f[p+1][1][i][x]=1;
			q.emplace(p+1,x,i);
		}
		tmp=f[p][1][x]&(f[p+1][1][y]^all);
		for(int i=tmp._Find_first();i<=n;i=tmp._Find_next(i)){
			a[p+1][i][y]=1;
			f[p+1][0][i][y]=f[p+1][1][y][i]=1;
			q.emplace(p+1,i,y);
		}
	}
	for(auto [x,y]:vec[lim]){
		b[0][x][y]=1;
		g[0][0][x][y]=g[0][1][y][x]=1;
		q.emplace(0,x,y);
	}
	rep(j,1,cur){
		while(q.size()&&q.front().p==j-1){
			auto [p,x,y]=q.front();
			q.pop();
			tmp=f[c[j]][0][y]&(g[j][0][x]^all);
			for(int i=tmp._Find_first();i<=n;i=tmp._Find_next(i)){
				b[j][x][i]=1;
				g[j][0][x][i]=g[j][1][i][x]=1;
				q.emplace(j,x,i);
			}
		}
		for(auto [x,y]:vec[c[j]]){
			tmp=g[j-1][1][x]&(g[j][1][y]^all);
			for(int i=tmp._Find_first();i<=n;i=tmp._Find_next(i)){
				b[j][i][y]=1;
				g[j][0][i][y]=g[j][1][y][i]=1;
				q.emplace(j,i,y);
			}
		}
	}
}
void Yorushika(){
	read(n,m,k),lim=__lg(k);
	int tmp=k;
	drep(i,lim,0){
		if(tmp>=(1<<i)){
			c[++cur]=i;
			tmp-=1<<i;
		}
	}
	mems(ans,0x3f);
	rep(t,1,m){
		int u,v;read(u,v);
		upd(u,v);
		rep(i,1,n){
			if(b[cur][1][i]){
				ans[i]=min(ans[i],t);
			}
		}
	}
	rep(i,1,n){
		printf("%d ",ans[i]>1e9?-1:ans[i]);
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

upd2：刚刚发现上面的实际上是 $O(\frac{n^3\log L}{\omega}+n^3)$ 的。这里再来一份 $O(\frac{n^3\log L}{\omega})$ 的。又快了 2ms。

int n,m,k,cur=-1,lim,ans[N],c[M];
int a[M][N][N],b[M][N][N];
bitset<N> f[M][2][N],g[M][2][N];
vector<pii> vec[M];
struct node{
	int p,x,y;
	node(int _p,int _x,int _y):p(_p),x(_x),y(_y){}
};
void upd(int u,int v,int t){
	queue<node> q;
	rep(i,0,lim){
		vec[i].clear();
	}
	bitset<N> tmp,all;
	all.set();
	f[0][0][u][v]=f[0][1][v][u]=1;
	q.emplace(0,u,v);
	while(q.size()){
		auto [p,x,y]=q.front();
		q.pop();
		vec[p].eb(x,y);
		if(p==lim){
			continue;
		}
		tmp=f[p][0][y]&(f[p+1][0][x]^all);
		for(int i=tmp._Find_first();i<=n;i=tmp._Find_next(i)){
			f[p+1][0][x][i]=f[p+1][1][i][x]=1;
			q.emplace(p+1,x,i);
		}
		tmp=f[p][1][x]&(f[p+1][1][y]^all);
		for(int i=tmp._Find_first();i<=n;i=tmp._Find_next(i)){
			f[p+1][0][i][y]=f[p+1][1][y][i]=1;
			q.emplace(p+1,i,y);
		}
	}
	for(auto [x,y]:vec[lim]){
		g[0][0][x][y]=g[0][1][y][x]=1;
		if(cur==0&&x==1){
			ans[y]=t;
		}
		q.emplace(0,x,y);
	}
	rep(j,1,cur){
		while(q.size()&&q.front().p==j-1){
			auto [p,x,y]=q.front();
			q.pop();
			tmp=f[c[j]][0][y]&(g[j][0][x]^all);
			for(int i=tmp._Find_first();i<=n;i=tmp._Find_next(i)){
				g[j][0][x][i]=g[j][1][i][x]=1;
				if(j==cur&&x==1){
					ans[i]=t;
				}
				q.emplace(j,x,i);
			}
		}
		for(auto [x,y]:vec[c[j]]){
			tmp=g[j-1][1][x]&(g[j][1][y]^all);
			for(int i=tmp._Find_first();i<=n;i=tmp._Find_next(i)){
				g[j][0][i][y]=g[j][1][y][i]=1;
				if(j==cur&&i==1){
					ans[y]=t;
				}
				q.emplace(j,i,y);
			}
		}
	}
}
void Yorushika(){
	read(n,m,k),lim=__lg(k);
	int tmp=k;
	drep(i,lim,0){
		if(tmp>=(1<<i)){
			c[++cur]=i;
			tmp-=1<<i;
		}
	}
	mems(ans,0x3f);
	rep(t,1,m){
		int u,v;read(u,v);
		upd(u,v,t);
	}
	rep(i,1,n){
		printf("%d ",ans[i]>1e9?-1:ans[i]);
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

以及你也可以尝试严格 $O(n^2\log L)$ 但是并不会快。

int n,m,k,cur=-1,lim,ans[N],c[M];
int a[M][N][N],b[M][N][N];
vector<pii> vec[M];
struct node{
	int p,x,y;
	node(int _p,int _x,int _y):p(_p),x(_x),y(_y){}
};
il int lg(__int128 x){
	return x>>60?__lg((ll)(x>>60))+60:__lg((ll)(x&((1ll<<60)-1)));
}
struct Bitset{
	__int128 x;
	Bitset(__int128 _x=0):x(_x){}
	il Bitset operator&(const Bitset &rhs)const{
		return Bitset(x&rhs.x);
	}
	il Bitset operator^(const Bitset &rhs)const{
		return Bitset(x^rhs.x);
	}
	il int get(int p){
		return x>>p&1;
	}
	il void set(int p){
		x|=(__int128)1<<p;
	}
	il int Find_first(){
		if(!x){
			return inf;
		}
		int ret=lg(x&(-x));
		x^=(__int128)1<<ret;
		return ret;
	}
}f[M][2][N],g[M][2][N];
void upd(int u,int v,int t){
	queue<node> q;
	rep(i,0,lim){
		vec[i].clear();
	}
	Bitset tmp,all;
	all.x=((__int128)1<<120)-1;
	f[0][0][u].set(v),f[0][1][v].set(u);
	q.emplace(0,u,v);
	while(q.size()){
		auto [p,x,y]=q.front();
		q.pop();
		vec[p].eb(x,y);
		if(p==lim){
			continue;
		}
		tmp=f[p][0][y]&(f[p+1][0][x]^all);
		for(int i=tmp.Find_first();i<=n;i=tmp.Find_first()){
			f[p+1][0][x].set(i),f[p+1][1][i].set(x);
			q.emplace(p+1,x,i);
		}
		tmp=f[p][1][x]&(f[p+1][1][y]^all);
		for(int i=tmp.Find_first();i<=n;i=tmp.Find_first()){
			f[p+1][0][i].set(y),f[p+1][1][y].set(i);
			q.emplace(p+1,i,y);
		}
	}
	for(auto [x,y]:vec[lim]){
		g[0][0][x].set(y),g[0][1][y].set(x);
		if(cur==0&&x==1){
			ans[y]=t;
		}
		q.emplace(0,x,y);
	}
	rep(j,1,cur){
		while(q.size()&&q.front().p==j-1){
			auto [p,x,y]=q.front();
			q.pop();
			tmp=f[c[j]][0][y]&(g[j][0][x]^all);
			for(int i=tmp.Find_first();i<=n;i=tmp.Find_first()){
				g[j][0][x].set(i),g[j][1][i].set(x);
				if(j==cur&&x==1){
					ans[i]=t;
				}
				q.emplace(j,x,i);
			}
		}
		for(auto [x,y]:vec[c[j]]){
			tmp=g[j-1][1][x]&(g[j][1][y]^all);
			for(int i=tmp.Find_first();i<=n;i=tmp.Find_first()){
				g[j][0][i].set(y),g[j][1][y].set(i);
				if(j==cur&&i==1){
					ans[y]=t;
				}
				q.emplace(j,i,y);
			}
		}
	}
}
void Yorushika(){
	read(n,m,k),lim=__lg(k);
	int tmp=k;
	drep(i,lim,0){
		if(tmp>=(1<<i)){
			c[++cur]=i;
			tmp-=1<<i;
		}
	}
	mems(ans,0x3f);
	rep(t,1,m){
		int u,v;read(u,v);
		upd(u,v,t);
	}
	rep(i,1,n){
		printf("%d ",ans[i]>1e9?-1:ans[i]);
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}