HackerEarth Completing Subgraphs problem solution

1. Given some interval of nodes [l,r] , you need to add edges between every pair of these nodes (even if they are already connected by an edge)
2. You need to remove all edges added in the ith query of type 1.
3. Given nodes u and v, you need to print the shortest path from u to v, or say that it doesn’t exist.

#include <bits/stdc++.h>
using namespace std;

#define PB push_back
#define MP make_pair


int n,m,q;
vector<pair<int,double> > adj[1000001];
int nodeptr;

bool useless_vertex[1000001]; //used for queries of type 2

int seencnt = 0;
void construct_segtree_1(int no, int b, int e){ //edges point toward parent
    seencnt=max(nodeptr+no,seencnt);
    //cout << "LUL " << no << endl;
    if(b==e){
        adj[b].PB(MP(nodeptr+no,0));
        //cout << "from " << b << " to " << nodeptr+no << endl;
    }else{
        adj[nodeptr+2*no].PB(MP(nodeptr+no,0));
        adj[nodeptr+2*no+1].PB(MP(nodeptr+no,0));
        //cout << "from " << nodeptr+2*no << " to " <<nodeptr+no << endl;
        //cout << "from " << nodeptr+2*no+1 << " to " <<nodeptr+no << endl;
        int mid = (b+e)/2;
        construct_segtree_1(2*no,b,mid);
        construct_segtree_1(2*no+1,mid+1,e);
    }
}
void construct_segtree_2(int no, int b, int e){ //edges point toward child
    seencnt=max(seencnt,nodeptr+no);
    //cout << "HAH " << nodeptr+no << endl;
    if(b==e){
        adj[nodeptr+no].PB(MP(b,0));
        //cout << "from " << nodeptr+no << " to " << b << endl;
    }else{
        adj[no+nodeptr].PB(MP(nodeptr+2*no,0));
        adj[no+nodeptr].PB(MP(nodeptr+2*no+1,0));
        //cout << "from " << nodeptr+no << " to " <<nodeptr+2*no << endl;
        //cout << "from " << nodeptr+no << " to " <<nodeptr+2*no+1 << endl;
        int mid = (b+e)/2;
        construct_segtree_2(2*no,b,mid);
        construct_segtree_2(2*no+1,mid+1,e);
    }
}
int nodeptrold;
int nodeptr2;
void search1(int no, int b, int e, int l, int r, int dummy){
    if(b>r || e<l) return;
    if(l<=b && e<=r){
        //insert edge to dummy
        //cout << "ADDED "<<no+nodeptrold << " TO " << dummy << endl;
        adj[no+nodeptrold].PB(MP(dummy,.5));
        return;
    }

    int mid = (b+e)/2;
    search1(2*no,b,mid,l,r,dummy);
    search1(2*no+1,mid+1,e,l,r,dummy);
}
void search2(int no, int b, int e, int l, int r, int dummy){
    if(b>r || e<l) return;
    if(l<=b && e<=r){
        //cout << "ADDED " <<dummy << " TO " << no+nodeptr2 << endl;
        adj[dummy].PB(MP(no+nodeptr2,.5));
        return;
    }
    int mid = (b+e)/2;
    search2(2*no,b,mid,l,r,dummy);
    search2(2*no+1,mid+1,e,l,r,dummy);
}

vector<int> dummyidxs;

bool myvis[1000001];
double dist[1000001];
int main()
{
    scanf("%d %d",&n,&m);

    for(int i=0; i < m; i++){
        int u,v;
        scanf("%d %d",&u,&v);
        u--; v--;
        adj[u].PB(MP(v,1));
        adj[v].PB(MP(u,1));
    }
    nodeptr = n-1;
    seencnt=n-1;
    construct_segtree_1(1,0,n-1);
    nodeptrold=nodeptr;
    nodeptr = seencnt;
    nodeptr2=nodeptr;
    construct_segtree_2(1,0,n-1);


    int q;
    scanf("%d",&q);
    for(int query=0;query<q;query++){
        int ty;
        scanf("%d",&ty);
        if(ty==1){
            int l,r;
            scanf("%d %d",&l,&r);
            l--; r--;
            seencnt++;
            search1(1,0,n-1,l,r,seencnt);
            search2(1,0,n-1,l,r,seencnt);
            dummyidxs.PB(seencnt);
        }else if(ty==2){
            int i;
            scanf("%d",&i);
            i--;
            assert(i<dummyidxs.size());
            useless_vertex[dummyidxs[i]]=true;
        }else if(ty==3){
            //dijkstra
            int u,v;
            scanf("%d %d",&u,&v);
            u--; v--;

            priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > > pq;
            pq.push(MP(0,u));
            for(int i=0;i<seencnt+1;i++) {
                myvis[i]=false;
                dist[i] = 100000000;
            }
            dist[u]=0;
            while(!pq.empty()){
                pair<double,int> po = pq.top();
                pq.pop();
                int vert = po.second;
                double tdis = po.first;
                if(useless_vertex[vert] || myvis[vert] || tdis-dist[vert]>1e-7) continue;
                myvis[vert]=true;
                for(pair<int,double> adjacent : adj[vert]){
                    int to = adjacent.first;
                    double ed = adjacent.second;
                    if(dist[vert]+ed<dist[to]){
                        dist[to]=dist[vert]+ed;
                        if(!myvis[to]) pq.push(MP(dist[to],to));
                    }
                }
            }
            if(!myvis[v]){
                cout << -1 << endl;
            }
            else cout << int(round(dist[v])) << endl;
        }
    }



}