AtCoder ABC #287 (ユニークビジョンプログラミングコンテスト2023 新春) : Ex - Directed Graph and Query

割と嫌いじゃない。
https://atcoder.jp/contests/abc287/tasks/abc287_h

問題

N個のラベル付き頂点からなる単純無向グラフが与えられる。
あるパスのコストは、パス上の頂点ラベルの最大値とする。

パスの始点-終点がQ個指定されるので、それぞれそのようなパスのコストの最小値を求めよ。

解法

bitsetを使いO(N^3+NQ)で解く。
以下の2テーブルを考える。
F(n,u) := 頂点uから、ラベルn以下の頂点だけを通り到達できる頂点の集合
G(n,u) := 頂点uに、ラベルn以下の頂点だけを通り到達できる頂点の集合

F(n-1,u)⊆F(n,u)なのは明らかなので、これらをbitsetで管理、in-placeで更新することを考える。
nを1～Nまで順にインクリメントしていきながらF(n,u)を更新し、またそのつど各クエリのパスが構成可能かチェックしよう。

F(n-1,*)とG(n-1,*)まで求められているとき、F(n,*)とG(n,*)を求めよう。
まずF(n,n)とG(n,n)を求める。

• n→v (ただしv＜n)となる辺があるとき、F(n,n) |= F(n-1,v)
• v→n (ただしv＜n)となる辺があるとき、G(n,n) |= G(n-1,v)

次に、以下の要領でF(n,*)とG(n,*)を更新していく。

• F(n,n)にvが含まれるならG(n,v) |= G(n,n)
• G(n,n)にvが含まれるならF(n,v) |= F(n,n)

int N,M;
vector<int> E[2020];
int C[2020][2020];
int Q;
bitset<2020> T[2020],TR[2020];
int U[10101],V[10101];
int R[10101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	scanf("%d%d",&N,&M);
	FOR(i,M) {
		scanf("%d%d",&x,&y);
		C[x-1][y-1]=1;
	}
	
	scanf("%d",&Q);
	FOR(i,Q) {
		scanf("%d%d",&x,&y);
		U[i]=x-1;
		V[i]=y-1;
		R[i]=1<<20;
	}
	
	FOR(i,N) {
		T[i][i]=1;
		TR[i][i]=1;
		FOR(x,N) if(C[i][x]) T[i]|=T[x];
		FOR(x,N) if(C[x][i]) TR[i]|=TR[x];
		FOR(x,N) if(TR[i][x]) T[x]|=T[i];
		FOR(x,N) if(T[i][x]) TR[x]|=TR[i];
		
		FOR(j,Q) {
			if(T[U[j]][V[j]]) R[j]=min(R[j],i+1);
		}
		
	}
	
	FOR(i,Q) {
		if(R[i]==1<<20) R[i]=-1;
		cout<<R[i]<<endl;
	}
	
}

まとめ

最初似非Warshal-Floydで解けないかと思って1WAしたのもったいなかったな。
bitsetで殴るのは個人的には割と好き。