kmjp's blog

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

AtCoder ARC #048 : D - たこ焼き屋とQ人の高橋君

実装は重いけど、考察はCより楽。
http://arc048.contest.atcoder.jp/tasks/arc048_d

問題

N頂点の木構造がある。
一部の頂点にはたこ焼きが配置されている。
頂点間を移動するとき、最初は1辺の移動に2の時間がかかるが、一度たこ焼きのある頂点を経由すると、以後移動にかかる時間が1になる。

(始点S[i],終点T[i])の対からなるクエリがQ個与えられる。
S[i]→T[i]に至る最短時間を求めよ。

解法

LCA+ダブリングで解いた。

グラフは木なので、たこ焼きを無視すると移動経路が一意に決まる。
あとは経路中のどこかで寄り道してたこ焼きを取るケースを考えよう。

頂点vに対し、最寄のたこ焼きがある頂点をf(v)とする。
DFSを2回行うと、各vに対しD(v,f(v))を求めることができる。

S→Tに至る途中頂点vで寄り道し、S→v→f(v)→v→Tと移動することを考えると、D(a,b)を頂点ab間の距離として移動にかかる時間はD(S,v)*2+D(v,f(v))*3+D(v,T)となる。
vを愚直に総当たりするとTLEする。

そこでグラフを根付き木と見なしダブリングを使おう。

以下の2値をダブリングで求める。

  • 頂点vから途中どこかでたこ焼きを拾い、2^a個親の頂点に登る最短時間UP(v,a)
  • 頂点vから2^a個親の頂点から途中どこかでたこ焼きを拾いvに降りる最短時間DOWN(v,a)

あとはS→LCA(S,T)に至る途中でたこ焼きを拾うケースの最短時間をUPを使って求め、またLCA(S,T)→Tに至る途中でたこ焼きを拾うケースの最短時間をDOWNを使って求め最小値を取る。

int N,Q;
vector<int> E[101010];
string S;
int MI[101010];

int P[21][200005],D[200005];
int upf[21][200005];
int upl[21][200005];

void dfs(int cur) {
	MI[cur]=(S[cur]==0)?10101010:0;
	
	ITR(it,E[cur]) if(*it!=P[0][cur]) {
		D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it);
		MI[cur]=min(MI[cur],MI[*it]+1);
	}
}

void dfs2(int cur,int p) {
	MI[cur]=min(MI[cur],p+1);
	ITR(it,E[cur]) if(*it!=P[0][cur]) dfs2(*it,MI[cur]);
	
	upf[0][cur]=upl[0][cur]=5000000;
	if(cur!=0) {
		upf[0][cur]=min(MI[cur]*3+1,2+MI[P[0][cur]]*3);
		upl[0][cur]=min(MI[cur]*3+2,1+MI[P[0][cur]]*3);
	}
}

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;
	
	cin>>N>>Q;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	cin>>S;
	FORR(r,S) r-='0';
	
	dfs(0);
	dfs2(0,505050);
	
	FOR(i,19) {
		FOR(x,N) {
			P[i+1][x]=P[i][P[i][x]];
			upf[i+1][x]=min(upf[i][x]+(1<<i),(2<<i)+upf[i][P[i][x]]);
			upl[i+1][x]=min(upl[i][x]+(2<<i),(1<<i)+upl[i][P[i][x]]);
		}
	}
	while(Q--) {
		int s,t;
		cin>>s>>t;
		s--,t--;
		int lc=lca(s,t);
		int ret=((D[t]-D[lc])+(D[s]-D[lc]))*2;
		if(s!=lc) {
			x=s;
			y=D[t]-D[lc];
			for(i=19;i>=0;i--) if(D[x]-D[lc]>=(1<<i)) {
				int p=getpar(x,1<<i);
				ret=min(ret,y+upf[i][x]+(D[p]-D[lc]));
				x=p;
				y+=2<<i;
			}
		}
		if(t!=lc) {
			x=t;
			y=2*(D[s]-D[lc]);
			for(i=19;i>=0;i--) if(D[x]-D[lc]>=(1<<i)) {
				int p=getpar(x,1<<i);
				ret=min(ret,y+upl[i][x]+2*(D[p]-D[lc]));
				x=p;
				y+=1<<i;
			}
		}
		cout<<ret<<endl;
	}
}

まとめ

HLは要らないと思った。