HackerEarth Weird Graph Query problem solution

In this HackerEarth Weird Graph Query problem solution, We are given a connected undirected weighted graph of N nodes and M edges. We are then given Q queries wherein each query we are given integers U, L, R, K. For every query we have to report the smallest integer C such that there are at least K nodes x such that L <= x <= R and the shortest distance from x to U is not more than C. 

HackerEarth Weird Graph Query problem solution.

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
//#define int long long
#define ld long double
#define vi deque<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define il pair<int,ll>
#define li pair<ll,int>
#define pll pair<ll,ll>
#define _path pair<ll,pair<ll,int> > 
#define vv deque
using namespace std;

const int MAXN = 1000+5;
const int INF = 1e9;

struct Node{
    int left;
    int right;
    int data;
    Node(){
        left = -1;
        right = -1;
        data = 0;
    }
};
Node buf[2000*1000*10];
int PTR;
int get(){
    return PTR++;
}
int get(int a,int b,int c){
    buf[PTR].left = a;
    buf[PTR].right = b;
    buf[PTR].data = c;
    return PTR++;
}

inline void expand(int node){
    if(buf[node].left == -1)buf[node].left = get();
    if(buf[node].right == -1)buf[node].right = get();
}
int update(int node,int ss,int se,int i,int val){
    if(i < ss or i > se)return node;
    if(ss == se){
        return get(-1,-1,val);
    }
    expand(node);
    
    int mid = (ss+se)/2;
    int x = update(buf[node].left,ss,mid,i,val);
    int y = update(buf[node].right,mid+1,se,i,val);
    return get(x,y,buf[x].data + buf[y].data);
}
int get(int node,int ss,int se,int l,int r){
    if(r < ss or l > se or node == -1)return 0;
    if(l <= ss and se <= r)return buf[node].data;
    int mid = (ss+se)/2;
    return get(buf[node].left,ss,mid,l,r) + get(buf[node].right,mid+1,se,l,r);
}

vv<ii> g[MAXN];
int dist[MAXN][MAXN];
vv<ii> allversions[MAXN];



void dijkstra(int source,int n){
    priority_queue<ii,vv<ii>,greater<ii> > pq;
    FOR(i,n)dist[source][i] = INF;
    pq.push({0,source});
    while(!pq.empty()){
        auto item = pq.top();pq.pop();

        if(dist[source][item.ss] <= item.ff)continue;
        dist[source][item.ss] = item.ff;
        for(auto e: g[item.ss]){
            if(item.ss+e.ss >= dist[source][e.ff])continue;
            pq.push({item.ff + e.ss,e.ff});
        }
    }
}

void buildPersSegtree(int x,int n){
    map<int,vi> all;
    FOR(i,n)all[dist[x][i]].pb(i); 

    
    allversions[x].pb({0,get()});
    
    for(auto e: all){
        int id = allversions[x].back().ss;
        for(auto f: e.ss){
            id = update(id,0,MAXN,f,1);
        }
        allversions[x].pb({e.ff,id});
    }
}


bool checkAnswer(int nodeU,int l,int r,int id,int k){
    return get(allversions[nodeU][id].ss,0,MAXN,l,r) >= k; 
}

int getAnswer(int node,int l,int r,int k){
    int low = 0;
    int high = allversions[node].size();
    high--;
    int best = allversions[node].back().ff;

    while(low <= high){
        int mid = (low + high)/2;
        if(checkAnswer(node,l,r,mid,k)){
            best = min(best,allversions[node][mid].ff);
            high = mid -1;
        }else{
            low = mid+1;
        }
    }

    return best;
}


void solve(){
    int n,m;
    cin >> n >> m;
    FOR(i,m){
        int a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    FOR(i,n)dijkstra(i,n);
    FOR(i,n)buildPersSegtree(i,n);

    int q;
    cin >> q;
    FOR(i,q){
        int u,l,r,k;
        cin >> u >> l >> r >> k;
        u--;l--;r--;
        cout << getAnswer(u,l,r,k) << endl;
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}