kmjp's blog

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

Maximum-Cup 2017: E - Interrupt Array

6問目までは調子が良かったね。
https://maximum-cup-2018.contest.atcoder.jp/tasks/maximum_cup_2018_e

問題

数列の初期状態をS={1}とする。
以下のクエリに順次答えよ。

  • i,jの2値が与えられるのでS[x]=iとなるxを1つ選び、i,j,iの3個と差し替える。なお、jは2から順に毎回インクリメントされた値が指定される。
  • i,jの2値が与えられるのでここまであり得るSのうち、S[a]=i、S[b]=jとa,bのうち|a-b|の最小値を求めよ。

解法

数値に対応したグラフを考える。
前者のクエリに対しiとjの間に辺を張ることにすると、このグラフは木をなす。
この木の間の距離が後者のクエリの解となる。

よってまずは全クエリのうち前者のタイプを処理して木を作り、LCAを求める準備をしよう。
あとは再度クエリを舐めてLCAを用いて後者を求めていけばよい。

int N;
string S[202020];
int X[202020],Y[202020];
int V=0;

vector<int> E[200005];
int P[21][200005],D[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;
	V=1;
	FOR(i,N) {
		cin>>S[i]>>X[i]>>Y[i];
		X[i]--;
		Y[i]--;
		if(S[i]=="A") {
			E[X[i]].push_back(Y[i]);
			V++;
		}
	}
	
	dfs(0);
	FOR(i,19) FOR(x,V) P[i+1][x]=P[i][P[i][x]];
	FOR(i,N) if(S[i]=="B") {
		cout<<dist(X[i],Y[i])-1<<endl;
	}
}

まとめ

何気にFA。