kmjp's blog

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

K4PC : C - 山登り(Mountain Climbing)

K4PCに参加。A,Bは順調に解けた後、Cでライブラリのバグや不足分が発覚。
その他グダグダで微妙な順位。
見せ場はAのFA位でした。
http://k4pc.contest.atcoder.jp/tasks/k4pc_c

問題

ある山の登山路が、辺に距離の付いた根付き木が与えられる。
山頂に上がる距離は、葉となるいずれかの頂点から根までの最短経路の最小値である。

ここでQ個のクエリが与えられる。
各クエリでは頂点番号が指定され、その頂点番号はその後利用不可能となる。

各クエリ実行後の登山路の状態について、山頂に上がる距離を答えよ。

解法

範囲を指定して値を更新したり、範囲を指定して最小値を求められるSegTreeを用いる。

まず最初に、根からDFSで頂点をたどり、根からの距離を求めるとともに、Euler-tourをしておく。
また、葉となる頂点において、根からの距離をSegTreeに格納しておく。

各クエリの結果、ある頂点が利用不可能となる場合、そのサブツリーに含まれる葉からは登頂不可能であるため、そのような範囲に対して、SegTreeの値を適当な最大値にすればよい。

後は毎回SegTreeを使って距離の最小値を求めればよい。

int N,Q;
int P[100001];
int W[100001];
ll C[100001];
vector<int> E[100001];
int D[100001],L[100001],R[100001];
int id;

template<class V,int NV> class SegTree_3 {
public:
	vector<V> val,mi;
	static V const def=1<<30, nolink=-1<<30;
	SegTree_3(){val.resize(NV*2); mi.resize(NV*2);clear();};
	void clear() { for(int i=0;i<NV*2;i++) val[i]=mi[i]=def; }
	V comp(V l,V r){ return min(l,r);};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return mi[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}

	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]=mi[k]=v;
		}
		else if(l < y && x < r) {
			if(val[k]!=nolink) mi[k*2]=mi[k*2+1]=val[k*2]=val[k*2+1]=val[k], val[k]=nolink;
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			mi[k]=comp(mi[k*2],mi[k*2+1]);
		}
	}
};

SegTree_3<int,1<<18> st;

void dfs(int cur,int d) {
	L[cur]=id++;
	D[cur]=d;
	int i;
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		dfs(tar,d+W[tar]);
	}
	R[cur]=id;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N-1) {
		cin>>x>>W[i+1];
		E[x-1].push_back(i+1);
	}
	dfs(0,0);
	
	FOR(i,N) {
		if(E[i].size()==0) st.update(L[i],L[i]+1,D[i]);
	}
	while(Q--) {
		cin>>x;
		x--;
		st.update(L[x],R[x],1<<30);
		y=st.getval(0,N);
		if(y>=1<<30) y=-1;
		cout<<y<<endl;
	}
}

まとめ

Euler-tourはすぐ思いついたが、範囲更新・範囲検索がSegTreeライブラリがなかったので大慌てで実装。
WAするわ時間をロスするわもったいなかったが、ライブラリが充実したので良しとしよう…。