HackerEarth Completing Subgraphs problem solution YASH PAL, 31 July 2024 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_pairint n,m,q;vector<pair<int,double> > adj[1000001];int nodeptr;bool useless_vertex[1000001]; //used for queries of type 2int 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 100005int 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