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するわ時間をロスするわもったいなかったが、ライブラリが充実したので良しとしよう…。