SLIMSHADYNICK's blog

ADA and Orange Tree SPOJ (LCA)
By SLIMSHADYNICK, history, 5 years ago, In English

I tried solving the problem the following way: 1) Using dfs I maintained the euler tour of the graph,height(or depth) of nodes,along with first and last occurence of index in euler tour. 2) Built a segment tree to give the minimum depth node in an interval along with its index. 3) Built another segment tree to give the number of different colors within an interval in the euler tour array.(I used Bitsets in java here). 4) for each query I calculate first the lca of the given nodes, call it X,using first segment tree. 5) then using first and last pos of X in the euler tour I calculate the number of different colors in this interval,using second segment tree.

But unfortunately I have been getting TLE at 15th test case. I tried optimising it a lot but its not working. Any help would be appreciated!

UPDATE: Instead of using segment tree to find the number of different color,instead for each node I calculated the number of different colors in a subtree using BitSet while dfs itself only. Now I'm calculating only the lca in log(n) time while answering the number of different colors in a subtree in O(1). But guess what? Now I'm getting NZEC on the same test case 15 which I don't get why:(. Any help would be appreciated:)

UPDATE: GOT accepted with c++ the same logic!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe you can make your solution slightly faster by replacing minimum segment tree with sparse table. Also it would be easier to help you if you share your source code.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    package LCA;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.BitSet;

public class AdaAndOrange_SPoj {
    public static void dfs(ArrayList<Integer> tree[],ArrayList<Integer> euler,int first[],
                           boolean visited[],int curr,int last[],int depth[]){
        visited[curr]=true;
        first[curr]=euler.size();
        last[curr]=euler.size();
        euler.add(curr);
        for(int j:tree[curr]){
            if(!visited[j]){
                depth[j]=depth[curr]+1;
                dfs(tree,euler,first,visited,j,last,depth);
                last[curr]=euler.size();
                euler.add(curr);
            }
        }
        return;
    }
    public static BitSet query(BitSet tree[],int s,int e,int l,int r,int treenode){
        if(s>r||e<l){
            return new BitSet();
        }
        if(s>=l&&e<=r){
            return tree[treenode];
        }
        int mid=(s+e)/2;
        BitSet left=(BitSet)query(tree,s,mid,l,r,2*treenode).clone();
        BitSet right=(BitSet)query(tree,mid+1,e,l,r,2*treenode+1).clone();
        left.or(right);
        return left;
    }
    public static void build(ArrayList<Integer> euler,int color[],BitSet tree[],int s,int e,int treenode){
//        System.out.println(s+" "+e+" "+treenode);
        if(s==e){
            tree[treenode]=new BitSet();
            tree[treenode].set(color[euler.get(s)]);
            return;
        }
        int mid=(s+e)/2;
        build(euler,color,tree,s,mid,2*treenode);
        build(euler,color,tree,mid+1,e,2*treenode+1);
        BitSet f=(BitSet)tree[2*treenode].clone();
        BitSet g=(BitSet)tree[2*treenode+1].clone();
        f.or(g);
        tree[treenode]=f;
        return;
    }
    public static Info2 query(Info2 tree[],int s,int e,int l,int r,int node){
        if(s>r||e<l){
            return new Info2(Integer.MAX_VALUE,0);
        }
        if(s>=l&&e<=r){
            return tree[node];
        }
        int mid=(s+e)/2;
        Info2 left=query(tree,s,mid,l,r,2*node);
        Info2 right=query(tree,mid+1,e,l,r,2*node+1);
        if(left.h<right.h){
            return left;
        }
        else{
            return right;
        }
    }
    public static void build2(int height[],Info2 segment[],int s,int e,int node,
                              ArrayList<Integer> euler){
        if(s==e){
            segment[node]=new Info2(height[euler.get(s)],euler.get(s));
            return;
        }
        int mid=(s+e)/2;
        build2(height,segment,s,mid,2*node,euler);
        build2(height,segment,mid+1,e,2*node+1,euler);
        if(segment[2*node].h<segment[2*node+1].h){
            segment[node]=segment[2*node];
        }
        else{
            segment[node]=segment[2*node+1];
        }
        return;
    }
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder print=new StringBuilder();
        int test=Integer.parseInt(br.readLine());
        while(test--!=0){
            String line[]=br.readLine().split(" ");
            int n=Integer.parseInt(line[0]);
            int q=Integer.parseInt(line[1]);
            int root=Integer.parseInt(line[2]);
            int color[]=new int[n];
            line=br.readLine().split(" ");
            ArrayList<Integer> tree[]=new ArrayList[n];
            for(int i=0;i<n;i++){
                color[i]=Integer.parseInt(line[i]);
                tree[i]=new ArrayList<>();
            }
            for(int i=1;i<n;i++){
                line=br.readLine().split(" ");
                int x=Integer.parseInt(line[0]);
                int y=Integer.parseInt(line[1]);
                tree[x].add(y);
                tree[y].add(x);
            }
            ArrayList<Integer> eulerr=new ArrayList<>();
            int first[]=new int[n];
            int last[]=new int[n];
            int depth[]=new int[n];
            dfs(tree,eulerr,first,new boolean[n],root,last,depth);
//           
            BitSet segmenttree[]=new BitSet[4*eulerr.size()+4];
            Info2 mintree[]=new Info2[4*eulerr.size()+4];
            build(eulerr,color,segmenttree,0,eulerr.size()-1,1);
            build2(depth,mintree,0,eulerr.size()-1,1,eulerr);
            while(q--!=0){
                line=br.readLine().split(" ");
                int x=Integer.parseInt(line[0]);
                int y=Integer.parseInt(line[1]);
                Info2 lca=query(mintree,0,eulerr.size()-1,Math.min(first[x],first[y]),
                        Math.max(first[x],first[y]),1);
                BitSet ans=query(segmenttree,0,eulerr.size()-1,first[lca.index],
                        last[lca.index],1);
                print.append(ans.cardinality()+"\n");
            }
        }
        System.out.print(print.toString());
    }
}

class Info2{
    int h,index;
    public Info2(int h,int index){
        this.h=h;
        this.index=index;
    }

}
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Won't the built time of sparse table hurt the complexity?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sparse table can be built in nlogn time but with it you can find LCA in O(1) time, so it's still same complexity but it would be faster because you answer queries faster and have less constant factor.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SLIMSHADYNICK (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SLIMSHADYNICK (previous revision, new revision, compare).

→ Reply