kmjp's blog

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

KUPC2015 : J - MODクエリ

その他コンテスト

本番方針はわかったけどバグが取れず時間切れ。
http://kupc2015.contest.atcoder.jp/tasks/kupc2015_j

問題

N頂点の木を成す無向グラフが与えられる。
各頂点iには整数A[i]が振られている。

この木に対し、以下のクエリQ個に答えよ。
j番目のクエリは頂点対U[j],V[j]及び整数X[j]からなる。
U[j]からV[j]に至る最短パス上の各頂点vについて、X[j] %= A[v]で順次剰余を取った最終的な値を答えよ。

解法

考え方としては、TCO R2Aの問題が近い。
TopCoderOpen 2015 Round2A Easy ModModMod - kmjp's blog


各クエリの値X[j]を全部まとめてU[j]→LCA(U[j],V[j])と一旦LCAまで上に移動し、その後LCA(U[j],V[j])→V[j]と降ろしていくことを考える。

上への移動パートでは、各頂点で(現在のX[j], クエリ番号j)のsetを持ち、(現在のX[j])が今いる頂点vにおけるA[v]以上のものは適宜剰余を取る。
上にsetの要素を移動する際は、マージテクを用いてsetの要素のコピーが生じないようにする。

下に移動するときも、同様にset内で値が大きいX[j]をA[v]で割っていく。
下に移動する際はマージテクの逆に分割する必要があるので、どのsubtreeに何個クエリの要素が含まれるかも計算しておくと良い。

int N,Q;
int A[101010];
int B[101010];
int C[101010];
int X[101010],V[101010],W[101010],LC[101010];
int OL[101010],OR[101010],eid;
int P[21][100005],D[100005];

vector<int> E[101010];
vector<int> QS[101010],QL[101010],QE[101010];
vector<int> DV[101010];
set<pair<int,int>> S[101010];
int nt[101010],nt2[101010];
set<pair<int,int> > SV;

void dfs(int cur) {
	OL[cur]=eid++;
	nt[cur]=QE[cur].size();
	DV[D[cur]].push_back(cur);
	ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it), nt[cur]+=nt[*it];
	OR[cur]=eid;
}

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 gomod(int r) {
	while(S[r].size()) {
		auto it=S[r].end();
		int q=(*--it).second;
		if(X[q]<A[r]) break;
		X[q] %= A[r];
		S[r].erase(it);
		S[r].insert({X[q],q});
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	FOR(i,N-1) {
		cin>>B[i]>>C[i];
		E[B[i]-1].push_back(C[i]-1);
		E[C[i]-1].push_back(B[i]-1);
	}
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	FOR(i,Q) {
		cin>>X[i]>>V[i]>>W[i];
		V[i]--,W[i]--;
		LC[i]=lca(V[i],W[i]);
		QS[V[i]].push_back(i);
		QL[LC[i]].push_back(i);
		QE[W[i]].push_back(i);
		SV.insert({OL[W[i]],i});
	}
	for(i=N;i>=0;i--) FORR(r,DV[i]) {
		int mav=-1, tar=-1;
		FORR(e,E[r]) if(D[e]==D[r]+1 && (int)S[e].size()>mav) mav=S[e].size(),tar=e;
		if(mav>=0) {
			swap(S[r],S[tar]);
			FORR(e,E[r]) if(D[e]==D[r]+1 && e!=tar) {
				FORR(ss,S[e]) S[r].insert(ss);
				S[e].clear();
			}
		}
		FORR(q,QS[r]) S[r].insert({X[q],q});
		gomod(r);
		FORR(q,QL[r]) S[r].erase({X[q],q});
	}
	
	FOR(i,N+1) FORR(r,DV[i]) {
		FORR(q,QL[r]) S[r].insert({X[q],q});
		gomod(r);
		FORR(q,QE[r]) S[r].erase({X[q],q}),SV.erase({OL[W[q]],q});
		
		int mav=-1, tar=-1;
		FORR(e,E[r]) if(D[e]==D[r]+1 && nt[e]>mav) mav=nt[e],tar=e;
		
		FORR(e,E[r]) if(D[e]==D[r]+1 && tar!=e) {
			for(auto sit=SV.lower_bound({OL[e],0});sit!=SV.end() && sit->first<OR[e];sit++) {
				int ss=sit->second;
				if(S[r].count({X[ss],ss})) S[e].insert({X[ss],ss}), S[r].erase({X[ss],ss});
			}
		}
		if(tar!=-1) swap(S[tar],S[r]);
	}
	
	
	FOR(i,Q) _P("%d\n",X[i]);

}

まとめ

本番は下りのマージテク(分解テク？)でバグを入れてしまい間に合わず…もったいない。