kmjp's blog

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

AtCoder AGC #005 : E - Sugigma : The Showdown

コードは短め。
http://agc005.contest.atcoder.jp/tasks/agc005_e

問題

N頂点と(N-1)本の赤い無向辺、(N-1)本の青い無向辺からなるグラフが与えられる。
赤い辺及び青い辺は、それぞれN頂点の木を形成する。
2人のプレイヤーがそれぞれ初期状態として頂点X,Yにいる。
それぞれ交互に自分の手番が来る。その際今いる頂点に居続けても良いし、赤・青辺で隣接する頂点に移動できる。

後手のプレイヤーが先手と同じ頂点に来たらゲーム終了である。
先手は手番数を最大化、後手は最小化しようと移動するとき、何手目で終了するか、もしくは永遠に終了しないか答えよ。

解法

青辺に関し頂点Yを根とする木を考える。
後手はこの木を根から順に下りてくるので、深さD[x]の頂点xには2*D[x]回目の手番で到達する。

あとは先手について、ダイクストラ法等の要領で赤辺を伝い各頂点に到達する最小の手番数を求めていこう。
その際、もちろん後手が先に到達する頂点は移動できない。
先手が到達可能な頂点群のうち最深の頂点xに対しD[x]を答えればよい。

また、先手が到達可能な頂点のうち、赤辺では隣接するが青辺では距離が3以上あるような頂点対が存在する場合、その2頂点を行き来すると先手は永遠に逃げることができる。

int N;
int X,Y;
vector<int> E[202020],E2[202020];

int P[21][200005],D[200005],D2[200005];

void dfs(int cur) {
	ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it);
}
int dist(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 D[a]+D[b]-2*D[(aa==bb)?aa:P[0][aa]];  // dist
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	FOR(i,N-1) {
		cin>>x>>y;
		E2[x].push_back(y);
		E2[y].push_back(x);
	}
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	P[0][Y]=Y;
	dfs(Y);
	FOR(i,19) FOR(x,N) P[i+1][x+1]=P[i][P[i][x+1]];
	FOR(i,N) D2[i+1]=10101010;
	
	int ret=0;
	queue<int> Q;
	D2[X]=0;
	Q.push(X);
	while(Q.size()) {
		x = Q.front();
		Q.pop();
		ret=max(ret,D[x]);
		if(D2[x]>=D[x]) continue;
		FORR(e,E2[x]) {
			if(dist(x,e)>=3) return _P("-1\n");
			if(D2[e]>D2[x]+1) D2[e]=D2[x]+1, Q.push(e);
		}
	}
	
	cout<<ret*2<<endl;
	
}

まとめ

考察するとコードが短くなる問題はいいね。