kmjp's blog

競技プログラミング参加記です

Codeforces #892 : Div2 F. Teleportation in Byteland

Codeforces

ちょっと実装がややこしい。
https://codeforces.com/contest/1859/problem/F

問題

根付き木が与えられる。
各辺には重みwがある。
プレイヤーのスキルがcの時、辺に沿って移動するコストはceil(w/c)とする。

いくつかの点では、コストTを払いcを倍にすることができる。
頂点対(u,v)からなるクエリがQ個与えられる。
各クエリについて、プレイヤースキル1の人が頂点uからvに移動する最小総コストを求めよ。

解法

スキル倍化は、1つの頂点で繰り返すのが最適。
また、倍化は高々O(log(max(W)))回程度しか行わない。
よって倍化回数を総当たりしよう。

まず各頂点について、最寄の倍化可能な頂点に行って倍化して戻る最小コストを求めよう。
次にダブリングで各点について以下を求める。

  • 点vからvの2^n個親の頂点に、c=1の状態で至る最小コスト
  • 点vからvの2^n個親の頂点に、c=1の状態から途中スキル倍化して至る最小コスト
  • 点vの2^n個親の頂点から、点vに、c=1の状態から途中スキル倍化して至る最小コスト
  • スキル倍化した状態で、点vの2^n個親の頂点から、点vに至る最小コスト

これらを用いて、u→LCA(u,v)→vと至る過程でどこかスキル倍化しながら移動する最小コストを計算すればよい。

int T;
int N,t,Q;
vector<pair<int,int>> E[200005];
int P[21][200005],D[200005];
ll H[21][202020];

ll dist[202020];
ll mi1[21][202020],mi2[21][202020];
string S;
int A[202020],B[202020],lc[202020];
ll mi[202020];

void dfs(int cur) {
	int i;
	FORR2(e,c,E[cur]) if(e!=P[0][cur]) {
		D[e]=D[cur]+1;
		P[0][e]=cur;
		FOR(i,21) H[i][e]=H[i][cur]+((c+(1<<i)-1)>>i);
		dfs(e);
	}
}
int getpar(int cur,int up) {
	int i;
	FOR(i,20) if(up&(1<<i)) cur=P[i][cur];
	return cur;
}

int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>t;
		FOR(i,N) {
			E[i].clear();
		}
		FOR(i,N-1) {
			cin>>x>>y>>k;
			E[x-1].push_back({y-1,k});
			E[y-1].push_back({x-1,k});
		}
		cin>>S;
		

		//0以外を根にするならP[0][root]=rootが必要
		dfs(0);
		FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
		cin>>Q;
		FOR(i,Q) {
			cin>>A[i]>>B[i];
			A[i]--;
			B[i]--;
			lc[i]=lca(A[i],B[i]);
			mi[i]=H[0][A[i]]+H[0][B[i]]-2*H[0][lc[i]];
		}
		
		FOR(i,21) {
			priority_queue<pair<ll,int>> PQ;
			FOR(j,N) {
				if(S[j]=='1') {
					dist[j]=t*i;
					PQ.push({-t*i,j});
				}
				else {
					dist[j]=1LL<<60;
				}
			}
			while(PQ.size()) {
				ll co=-PQ.top().first;
				int cur=PQ.top().second;
				PQ.pop();
				if(co!=dist[cur]) continue;
				FORR2(e,c,E[cur]) if(chmin(dist[e],co+c+((c+(1<<i)-1)>>i))) PQ.push({-dist[e],e});
			}
			FOR(j,N) {
				mi1[0][j]=-H[0][j]+dist[j]+H[i][j];
				mi2[0][j]=H[0][j]+dist[j]-H[i][j];
			}
			FOR(k,20) FOR(j,N) {
				mi1[k+1][j]=min(mi1[k][j],mi1[k][P[k][j]]);
				mi2[k+1][j]=min(mi2[k][j],mi2[k][P[k][j]]);
			}
			
			FOR(k,Q) {
				mi[k]=min(mi[k],H[0][A[k]]+H[i][B[k]]-H[0][lc[k]]-H[i][lc[k]]+dist[lc[k]]);
				x=A[k];
				y=D[A[k]]-D[lc[k]];
				FOR(j,20) if(y&(1<<j)) {
					mi[k]=min(mi[k],H[0][A[k]]+H[i][B[k]]-2*H[i][lc[k]]+mi1[j][x]);
					x=P[j][x];
				}
				x=B[k];
				y=D[B[k]]-D[lc[k]];
				FOR(j,20) if(y&(1<<j)) {
					mi[k]=min(mi[k],H[0][A[k]]+H[i][B[k]]-2*H[0][lc[k]]+mi2[j][x]);
					x=P[j][x];
				}
			}
		}
		FOR(i,Q) cout<<mi[i]<<endl;
	}
}

まとめ

わかってしまえば自然なアプローチ。