PKU 1986 Distance Queries
LCA求めて距離出すだけ。
最初Navigation Nightmareのinputの形式と同じなのでマンハッタン距離かなぁと思っていたけど入力の方角関係ないらしい。意味不明。
最初ダブリングでやったらなぜかTLEが取れなかったのでeuler tour+RMQで書きなおしたら通った。
両方logNなのになんで間に合わないのか…闇。一応自分なりに考えたことを書いておくと、
ダブリングをするときのparの計算量がO(16*N),RMQの構築はO(2*N)程度なのでそこの差なのかなぁと。
構築した後は各クエリごとに両方O(logN)なのであんまり差は無さそう。
正しい理由がわかる方がいらっしゃったら教えてください。
適当にぱぱっと実装してコンパイルしたら何もエラーでなくて逆にびびった…
数日前にPKUを真面目にとこうと思ったのに、中間直前。
中間は害悪。中間後からはどんどん解こうと思います。
struct edge{int to,cost;}; const int SIZE=1<<17; int N,M,K; int k=0; vector<edge> G[40010]; int depth[80010]; int dist[40010]; int vs[80010]; int id[40010]; P seg[SIZE*2]; void add_edge(int a,int b,int c) { edge e; e.to=b;e.cost=c; G[a].pb(e); e.to=a; G[b].pb(e); } void dfs(int v,int p,int d) { id[v]=k; vs[k]=v; depth[k++]=d; for(int i=0;i<G[v].size();i++) { if(G[v][i].to!=p) { dist[G[v][i].to]=dist[v]+G[v][i].cost; dfs(G[v][i].to,v,d+1); vs[k]=v; depth[k++]=d; } } } void construct_rmq() { for(int i=0;i<k;i++)seg[i+SIZE-1]=mp(depth[i],i); for(int i=SIZE-2;i>=0;i--)seg[i]=min(seg[i*2+1],seg[i*2+2]); } P query(int a,int b,int k=0,int l=0,int r=SIZE) { if(r<=a||b<=l)return mp(INF,-1); else if(a<=l&&r<=b)return seg[k]; else return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r)); } int lca(int u,int v) { if(id[u]>id[v])swap(u,v); return vs[query(id[u],id[v]+1).sec]; } int main() { scanf("%d %d",&N,&M); for(int i=0;i<M;i++) { char ig; int a,b,c; scanf("%d %d %d %c",&a,&b,&c,&ig); add_edge(a,b,c); } dfs(1,-1,0); construct_rmq(); scanf("%d",&K); for(int i=0;i<K;i++) { int u,v; scanf("%d %d",&u,&v); int w=lca(u,v); printf("%d\n",dist[u]+dist[v]-dist[w]*2); } return 0; }