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。