HackerEarth Completing Subgraphs problem solution

In this HackerEarth Completing Subgraphs problem solution There’s some unweighted graph with N nodes and M edges. You have to respond to queries of 3 forms:

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)
You need to remove all edges added in the ith query of type 1.
Given nodes u and v, you need to print the shortest path from u to v, or say that it doesn’t exist.

HackerEarth Completing Subgraphs problem solution.

#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;
        }
    }



}

Second solution

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

#define ii pair<int, int>
#define ff first
#define ss second 
#define N 100005

int n, curr, memo[N], spoilt[10 * N], D[10 * N];;
vector<ii> v[10 * N];
int tree[2][4 * N];

int get(int node, int idx){
  if(!idx)
    return n + node;
  return 5 * n + node;
}

void build_tree(int idx, int node, int l, int r){
  if(l == r){
    if(!idx)
      v[l].push_back(ii(get(node, idx), 0));
    else
      v[get(node, idx)].push_back(ii(l, 0));
    return;
  }
  int m = (l + r) >> 1;
  build_tree(idx, 2 * node, l, m);
  build_tree(idx, 2 * node + 1, m + 1, r);
  if(!idx){
    v[get(2 * node, idx)].push_back(ii(get(node, idx), 0));
    v[get(2 * node + 1, idx)].push_back(ii(get(node, idx), 0));
  }
  else{
    v[get(node, idx)].push_back(ii(get(2 * node, idx), 0));
    v[get(node, idx)].push_back(ii(get(2 * node + 1, idx), 0));
  }
}

void edge_adder(int idx, int node, int l, int r, int a, int b, int vertex){
  if(b < l || r < a)
    return;
  if(a <= l && r <= b){
    if(!idx)
      v[get(node, idx)].push_back(ii(vertex, 1));
    else
      v[vertex].push_back(ii(get(node, idx), 1));
    return;
  }
  int m = (l + r) >> 1;
  edge_adder(idx, 2 * node, l, m, a, b, vertex);
  edge_adder(idx, 2 * node + 1, m + 1, r, a, b, vertex);
}


void dijkstra(int s)
{
  for (int i = 0; i < curr; ++i)  D[i] = INT_MAX;
    priority_queue <ii> pq;
  D[s] = 0;
    pq.push(make_pair(0 , s));
    while(!pq.empty()){
        int node = pq.top().second;
        long long cost = -pq.top().first;
        pq.pop();
        if(D[node] < cost){
            continue;
        }
        for(auto it : v[node]){
            int next = it.first;
            long long d = cost + it.second;
            if(spoilt[next])
              continue;
            if(D[next] > d){
                D[next] = d;
                pq.push(make_pair(-d , next));
            }
        }
    }
}

int main(){
  int i, j, m, a, b, q, t, it;
  scanf("%d %d", &n, &m);
  for(i = 0; i < m; i++){
    scanf("%d %d", &a, &b);
    v[a].push_back(ii(b, 2));
    v[b].push_back(ii(a, 2));
  }
  build_tree(0, 1, 1, n);
  build_tree(1, 1, 1, n);

  curr = 9 * n + 1;
  it = 1;
  scanf("%d", &q);
  while(q--){
    scanf("%d", &t);
    if(t == 1){
      scanf("%d %d", &a, &b);
      edge_adder(0, 1, 1, n, a, b, curr);
      edge_adder(1, 1, 1, n, a, b, curr);
      memo[it++] = curr;
      curr++;
    }
    else if(t == 2){
      scanf("%d", &a);
      spoilt[memo[a]] = 1;
    }
    else if(t == 3){
      scanf("%d %d", &a, &b);
      dijkstra(a);
      (D[b] == INT_MAX)
        ? printf("-1n")
        : printf("%dn", D[b] / 2);
    }
  }
    
    return 0;
}

coding problems solutions