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