2
\$\begingroup\$

This is my implementation of lowest common ancestor problem,I tried to solve it using square root decomposition

pre processing time : O(n)

query time:O(sqrt(h))
h -> height of tree

This was LCA on spoj

Well i added comments in my code and My approach very well explained here with every line of code https://www.geeksforgeeks.org/sqrt-square-root-decomposition-set-2-lca-tree-osqrth-time/

You can see in the comments of spoj that many people O(n) query is getting accepted. But mine is O(sqrt(n)) and is not accepted getting TLE.

Please help me where i am doing wrong ?

#include<bits/stdc++.h>
using namespace std;
#define MAXN 2000
int block_sz;
int depth[MAXN];
int parent[MAXN];
int jump_parent[MAXN];
int hmax;
///jump_parent is first ancestor
///of current node

vector <int> adj[MAXN];
void addEdge(int u,int v){
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int lca_naive(int u,int v){
    if(u==v){
        return u;
    }
    if(depth[u]>depth[v])
        swap(u,v);
    v=parent[v];
    return lca_naive(u,v);
}
// precalculating the required parameters 
// associated with every node 
void dfs(int cur,int prev){
    depth[cur]=depth[prev]+1;
    parent[cur]=prev;
    //hmax=max(height,hmax);
///suppose if h=9,then sqrt(h)=3
///in that case total blocks will be
///0 to 3-1
/// so rem will be zero for only first element in the current block
    if(depth[cur] % block_sz == 0){
        jump_parent[cur]=parent[cur];
    }
    else{
        jump_parent[cur]=jump_parent[prev];
    }
    for(int i=0;i<adj[cur].size();i++){
        if(adj[cur][i]!=prev){
            dfs(adj[cur][i],cur);
        }
    }
}
int lcasqrt(int u,int v){
    while(jump_parent[u]!=jump_parent[v]){
        if(depth[u]>depth[v])
            swap(u,v);
        v=jump_parent[v];
    }
    return lca_naive(u,v);
}
void preprocess(int height){
    block_sz=sqrt(height);
    depth[0]=-1;

    dfs(1,0);
}
///seperate dfs to calculate height
void dfs_height(int cur,int prev,int height){
    hmax=max(height,hmax);
    for(int i=0;i<adj[cur].size();i++){
        if(adj[cur][i]!=prev)
            dfs_height(adj[cur][i],cur,height+1);
    }
}
int main(int argc, char const *argv[])
{
    // adding edges to the tree
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            int m;
            cin>>m;
            for(int j=1;j<=m;j++){
                int v;
                cin>>v;

                adj[i].push_back(v);
            }
        }
        dfs_height(1,0,0);
        preprocess(hmax);
        dfs(1,0);
        int q;
        cin>>q;
        for(int i=0;i<q;i++){
            int u,v;
            cin>>u>>v;
            cout<<lcasqrt(u,v)<<endl;

        }


    }
}
\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to Code Review! This question is incomplete. To help reviewers give you better answers, please add sufficient context to your question. The more you tell us about what your code does and what the purpose of doing that is, the easier it will be for reviewers to help you. Questions should include a description of what the code does \$\endgroup\$ – Edward Mar 17 at 11:27
  • \$\begingroup\$ For each test case print Q + 1 lines, The first line will have “Case C:” without quotes where C is the case number starting with 1 \$\endgroup\$ – outoftime Mar 17 at 12:17
  • \$\begingroup\$ #include<bits/stdc++.h> is bad habit. \$\endgroup\$ – πάντα ῥεῖ Mar 17 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.