JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor pku 1986 Distance Queries TLEEE
 pku 1986 Distance Queries TLEEE | Reply I need help :P a lot of TLEI tried to solve this using a segment tree in the following way.First, I read the tree and do a bfs in order to relabel the verteces such that a vertex with a less label than other is in the same depth level or above.Then, I do a dfs travelsal, as it is depicted in the tutorial and create to arrays, the first array recvertex has the labels of the verteces visited in the traversal, and the vector recedge has the values of the edges visited, such that if an edge is visited in a forward way, its value is positive, but if the edge is in a backtracking way, its value is negative. An also, the first value of the recedge array is 0, because it has no cost to reach the vertex 0. Besides,I have an array occurs that has, for each vertex, its first occurence in the recvertex array.After that, I create a segment tree for recvertex, which will give the lower common ancestor of two verteces.And finally, for each query, I read the two verteces, get their label values, get their lower common ancestor, and calculate the distance between both verteces.Well, I have a lot of tle, I have tested with some input data from usaco and it seems to solve it well, but the tle is there.I copy my code here```#include #include #include #include #include #include using namespace std; typedef int ll; #define N 500000 #define NN 100000 vector > adj2; vector > wadj2; int recvertex[N],recedge[N],occurs[NN],segmentmin[N],bit[NN]; int recvertexsz=0,recedgesz=0;   void updatemin(int pos,int by,int node=0,int lo=0,int hi=recvertexsz-1){ segmentmin[node]=min(segmentmin[node],by); if(lo=pos) updatemin(pos,by,node*2+1,lo,mid); else updatemin(pos,by,node*2+2,mid+1,hi); } }   int querymin(int from,int to,int node=0,int lo=0,int hi=recvertexsz-1){ if(from>to) return 1<<30; if(from==lo&&to==hi) return segmentmin[node]; int mid=(lo+hi)/2; return min(querymin(from,min(to,mid),node*2+1,lo,mid), querymin(max(mid+1,from),to,node*2+2,mid+1,hi)); }   void dfs(int u){ recvertex[recvertexsz++]=u; if(u==0) recedge[recedgesz++]=0; occurs[u]=recvertexsz-1; for(int i=0;i>n>>m; vector > adj(n);//adjacence list vector > wadj(n);//weigth adjacence list for(int i=0;i>k; //each query while(k--){ int a,b; scanf("%d %d",&a,&b); a--;b--; a=label[a]; b=label[b]; if(occurs[a]>occurs[b]) swap(a,b); int low=querymin(occurs[a],occurs[b]); ll dist=bit[occurs[a]]-2*bit[occurs[low]]+bit[occurs[b]]; printf("%d\n",dist); } } ```I need your help, please xD. This is an important problem for learning and I will be very happy if I solve it.Thanks in advance =D
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor pku 1986 Distance Queries TLEEE Previous Thread  |  Next Thread