HackerRank Taxicab Driver’s problem solution

In this HackerRank Taxicab Driver’s problem solution you are given a city’s junctions and pathways. there is only one shortest path between each pair of junctions. we need to output the number of unordered pairs such that it is not possible to drive from i to j.

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

  static class Pair implements Comparable<Pair> {
    long fi;
    long se;
    
    public Pair(long fi, long se) {
      this.fi = fi;
      this.se = se;
    }

    @Override
    public int compareTo(Pair o) {
      if (fi != o.fi) {
        return fi > o.fi ? 1 : -1;
      }
      if (se == o.se) {
        return 0;
      }
      return se > o.se ? 1 : -1;
    }
  }
  
  static boolean[] cut;
  static int[] size;
  
  static int getSize(int v, int p) {
    size[v] = 1;
    for (int u: e[v]) {
      if (u != p && ! cut[u]) {
        size[v] += getSize(u, v);
      }
    }
    return size[v];
  }

  static Pair[] a;
  static List<Integer>[] e;
  static Pair[] b;
  
  static int getDist(int v, int p, int i, long hh, long vv) {
    hh += Math.abs(a[v].fi - a[p].fi);
    vv += Math.abs(a[v].se - a[p].se);
    b[i++] = new Pair(hh, vv);
    for (int u: e[v]) {
      if (u != p && ! cut[u]) {
        i = getDist(u, v, i, hh, vv);
      }
    }
    return i;
  }

  static public int lowerBound(long[] arr, int len, long key) {
    if (key <= arr[0]) {
      return 0;
    }
    if (key > arr[len - 1]) {
      return 0;
    }
    
    int index = Arrays.binarySearch(arr, 0, len, key);
    if (index < 0) {
      index = - index - 1;
      if (index < 0) {
        return 0;
      }
    } 
    while (index > 0 && arr[index-1] == key) {
      index--;
    }
    return index;
  }
  
  static int upperBound(long[] arr, int len, long key) {
    int index = Arrays.binarySearch(arr, 0, len, key);
    if (index < 0) {
      index = - index - 1;
      if (index < 0) {
        return 0;
      }    
      if (index >= len) {
        return len;
      }    
    }
    while (index < len && arr[index] == key) {
      index++;
    }
    return index;
  }

  static int[] fenwick;
  static long[] c;
  static long h;
  static long v;
  
  static long calc(int l, int r) {
    int n = r-l;
    long ret = 0;
    Arrays.sort(b, l, r);
    for (int i = l; i < r; i++) {
      c[i-l] = b[i].se;
    }
    Arrays.sort(c, 0, n);
    Arrays.fill(fenwick, 0, n, 0);
    for (int j = l, i = r; --i >= l; ) {
      for (; j < r && b[j].fi+b[i].fi <= h; j++)
        for (int x = lowerBound(c, n, b[j].se); x < n; x |= x+1) {
          fenwick[x]++;
        }
      for (int x = upperBound(c, n, v-b[i].se); x > 0; x &= x-1) {
        ret += fenwick[x-1];
      }
    }
    return ret;
  }
    
  
  static Object[] divide(int l, int v) {
    getSize(v, -1);
    int nn = size[v];
    int p = -1;
    for(;;) {
      int ch = -1;
      for (int u: e[v]) {
        if (u != p && ! cut[u] && 2*size[u] >= nn) {
          ch = u;
          break;
        }
      }
      if (ch < 0) {
        break;
      }
      p = v;
      v = ch;
    }
    cut[v] = true;
    b[l] = new Pair(0, 0);
    int i = l+1;
    long ret = 0;
    for (int u: e[v]) {
      if (! cut[u]) {
        Object[] r = divide(i, u);
        ret += (long)r[1];
        getDist(u, v, i, 0, 0);
        ret -= calc(i, (int)r[0]);
        i = (int)r[0];
      }
    }
    cut[v] = false;
    ret += calc(l, i) - 1;
    return new Object[]{i, ret};
  }
 
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    h = Long.parseLong(st.nextToken());
    v = Long.parseLong(st.nextToken());

    a = new Pair[n];
    e = new List[n];
    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      long fi = Long.parseLong(st.nextToken());
      long se = Long.parseLong(st.nextToken());

      a[i] = new Pair(fi, se);
      e[i] = new LinkedList<>();
    }

    for (int i = 0; i < n - 1; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken()) - 1;
      int v = Integer.parseInt(st.nextToken()) - 1;

      e[u].add(v);
      e[v].add(u);
    }

    cut = new boolean[n];
    size = new int[n];
    b = new Pair[n];
    fenwick = new int[n];
    c = new long[n];
    long result = (long)(n-1)*n - ((long)divide(0, 0)[1]) >> 1;
    bw.write(String.valueOf(result));
    bw.newLine();
    bw.close();
    br.close();
  }
}

Problem solution in C++ programming.

#include <bits/stdc++.h>

#define FO(i,a,b) for (int i = (a); i < (b); i++)
#define sz(v) int(v.size())

using namespace std;

typedef long long ll;

typedef pair<ll,ll> E;
#define dx first
#define dy second
struct edge {
    int o;
    ll dx, dy;

    edge(int o=0, ll dx=0, ll dy=0) : o(o), dx(dx), dy(dy) {}
};

vector<edge> u[100005];
int n; ll DX, DY;
ll Y[100005], X[100005];
int sc[100005];

void delete_from(int x, int y) {
    FO(i,0,sz(u[x])) if (u[x][i].o == y) {
        swap(u[x][i],u[x].back());
        u[x].pop_back();
        return;
    }
}

void delete_node(int x) {
    FO(i,0,sz(u[x])) {
        delete_from(u[x][i].o,x);
    }
}

void resetsc(int x, int p) {
    sc[x] = 1;
    FO(i,0,sz(u[x])) if (u[x][i].o != p) {
        resetsc(u[x][i].o,x);
        sc[x] += sc[u[x][i].o];
    }
}

int find_centre(int x, int p, int tsz) {
    int lsz = tsz-sc[x];
    FO(i,0,sz(u[x])) if (u[x][i].o != p) {
        lsz = max(lsz, sc[u[x][i].o]);
        int y = find_centre(u[x][i].o,x,tsz);
        if (y != -1) return y;
    }
    if (2*lsz <= tsz+5) return x;
    return -1;
}

void getl(int x, int p, vector<E> &v, ll dx, ll dy) {
    if (dx != 0 || dy != 0) v.push_back(E(dx,dy));
    FO(i,0,sz(u[x])) if (u[x][i].o != p) {
        getl(u[x][i].o, x, v, dx+u[x][i].dx, dy+u[x][i].dy);
    }
}

bool cmp(E a, E b) {
    if (a.dx != b.dx) return a.dx < b.dx;
    else return a.dy < b.dy;
}

ll res;
vector<ll> bit;

void ub(int y, int dv) {
    for (;y<sz(bit);y+=y&-y) bit[y] += dv;
}

ll qb(int y) {
    ll r = 0;
    for (;y>0;y-=y&-y) r += bit[y];
    return r;
}

ll doitbf(vector<E> p) {
    ll RES = 0;
    FO(i,0,sz(p)) FO(j,0,i) if (p[i].dx+p[j].dx <= DX && p[i].dy+p[j].dy <= DY) RES++;
    return RES;
}

ll doit(vector<E> p) {
    //printf("DOITn");
    //FO(i,0,sz(p)) printf("%lld,%lldn", p[i].dx, p[i].dy);
    ll RES = 0;
    vector<E> q;
    vector<ll> y;
    FO(i,0,sz(p)) {
        if (p[i].dx+p[i].dx <= DX && p[i].dy+p[i].dy <= DY) RES--;
        ll qdx = DX-p[i].dx;
        ll qdy = DY-p[i].dy;
        if (qdx >= 0 && qdy >= 0) q.push_back(E(qdx, qdy));
    }
    FO(i,0,sz(p)) y.push_back(p[i].dy);
    FO(i,0,sz(q)) y.push_back(q[i].dy);
    sort(y.begin(),y.end());
    y.resize(unique(y.begin(),y.end())-y.begin());
    bit.resize(sz(y)+5);
    FO(i,0,sz(bit)) bit[i] = 0;

    sort(p.begin(),p.end(),cmp);
    sort(q.begin(),q.end(),cmp);

    int pi = 0, qi = 0;
    while (qi < sz(q)) {
        if (pi < sz(p) && !cmp(q[qi],p[pi])) {
            int yv = lower_bound(y.begin(),y.end(),p[pi].dy)-y.begin()+1;
            ub(yv,1);
            pi++;
        } else {
            int yv = lower_bound(y.begin(),y.end(),q[qi].dy)-y.begin()+1;
            RES += qb(yv);
            qi++;
        }
    }
    RES /= 2;

    return RES;
}

void testdoit() {
    vector<E> v;
    DX = DY = 100;
    FO(i,0,1000) v.push_back(E(rand()%DX,rand()%DY));
    printf("%lld %lldn", doit(v), doitbf(v));
}

void solve(int x) {
    if (sz(u[x]) == 0) return;
    resetsc(x,-1);
    x = find_centre(x,-1,sc[x]);
    vector<E> cv;
    cv.push_back(E(0,0));
    FO(i,0,sz(u[x])) {
        vector<E> v;
        getl(u[x][i].o,x,v,u[x][i].dx,u[x][i].dy);
        res -= doit(v);
        FO(j,0,sz(v)) cv.push_back(v[j]);
    }
    res += doit(cv);
    delete_node(x);
    FO(i,0,sz(u[x])) solve(u[x][i].o);
}

int main() {
    //testdoit();
    //return 0;

    scanf("%d %lld %lld", &n, &DX, &DY);
    FO(i,0,n) {
        scanf("%lld %lld", &X[i], &Y[i]);
    }
    FO(i,0,n-1) {
        int a,b; scanf("%d %d", &a, &b); a--; b--;
        u[a].push_back(edge(b,abs(X[a]-X[b]),abs(Y[a]-Y[b])));
        u[b].push_back(edge(a,abs(X[a]-X[b]),abs(Y[a]-Y[b])));
    }
    solve(0);
    ll T = (n * 1ll * (n-1)) / 2;
    printf("%lldn", T - res);
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define have(self, id) ((self)[(id) >> 5] &  (1U << ((id) & 31U)))
#define inv(self, id)  ((self)[(id) >> 5] ^= (1U << ((id) & 31U)))   

static inline unsigned delta(unsigned self, unsigned other) {
    return (self < other) ? (other - self) : (self - other);
}

void ascending_stbl(unsigned length, unsigned long *weights, unsigned *self) {
    unsigned 
        at, span,
        at_left, at_right,
        *left, *right,
        order[length];

    for (span = 1; span < length; span <<= 1)         
        for (left = &((unsigned *)memcpy(order, self, sizeof(order[0]) * length))[at = length]; at > span; ) {
            right = left - (at_right = span);            
            at_left = (at < (span << 1)) ? (at - span) : span;            

            for (left -= at_left + at_right; at_left && at_right; 
                self[--at] = (weights[left[at_left - 1]] > weights[right[at_right - 1]]) 
                                       ? left[--at_left] : right[--at_right]);           

            memcpy(&self[at -= (at_left | at_right)], right, at_right * sizeof(self[0]));      
        }        
}


int main() {    
    unsigned vertex_cnt;
    unsigned long limits[2];     
    scanf("%u %lu %lu", &vertex_cnt, &limits[0], &limits[1]);
    
    unsigned            
        cords[2][vertex_cnt],                                                                   
        neighbors[vertex_cnt << 1],        
        ancestors[vertex_cnt],
        indices[vertex_cnt + 2],        
        next, tail, others, at;

    for (at = 0; at < vertex_cnt; at++)
        scanf("%u %u", &cords[0][at], &cords[1][at]);
    
    for (at >>= 1; at--; ((unsigned long *)ancestors)[at] = 0x100000001UL * vertex_cnt);
    for (ancestors[at += vertex_cnt] = vertex_cnt; at--; ancestors[others] = tail)
        if (ancestors[(scanf("%u %u", &tail, &others), --tail, --others)] != vertex_cnt)
            for (tail ^= others, others ^= tail, tail ^= others; 
                 ancestors[others] != vertex_cnt; 
                 others = next
            ) {
                next = ancestors[others];
                ancestors[others] = tail;
                tail = others;
            }
    
    memset(indices, 0, sizeof(indices));
    for (at = vertex_cnt; at--; *(unsigned long *)&indices[ancestors[at]] += 0x100000001UL);    
    for (; ++at < (vertex_cnt >> 1); ((unsigned long *)indices)[at + 1] += ((unsigned long *)indices)[at]);
    for (at = vertex_cnt; at--; neighbors[--indices[ancestors[at]]] = at);

    unsigned 
        history[vertex_cnt],        
        weights[vertex_cnt + 1];

    at += vertex_cnt;
    history[at] = neighbors[at];
    for (others = 0; others < at; others++) {
        history[others] = history[at];
        at -= (indices[history[at] + 1] - indices[history[at]]) - 1U;
        memcpy(
            &history[at],
            &neighbors[indices[history[others]]],
            sizeof(history[0]) * (indices[history[others] + 1] - indices[history[others]])
        );
    }
    for (at = vertex_cnt >> 1; at--; ((unsigned long *)weights)[at] = 0x100000001UL);
    for (*(unsigned long *)&weights[(at = vertex_cnt) - 1] = 1UL; --at; 
        weights[ancestors[history[at]]] += weights[history[at]]);        
        
    unsigned 
        offsets[vertex_cnt + 2],        
        forward[vertex_cnt];  
    {
        unsigned 
            mass[vertex_cnt],
            centroids[vertex_cnt];  

        centroids[history[0]] = (mass[0] = vertex_cnt);        
        for (at = 1; at--; weights[next] = 0) {
            for (others = (tail = history[at]); (weights[others] << 1) < mass[at]; others = ancestors[tail = others]);
            for (others = indices[next = others]; others < indices[next + 1]; others++)
                if ((weights[neighbors[others]] << 1) > mass[at] && neighbors[others] != tail)
                    others = indices[next = neighbors[others]] - 1;
                        
            for (centroids[next] = centroids[history[at]]; others-- > indices[next]; )
                if (weights[neighbors[others]]) {                    
                    centroids[history[at] = neighbors[others]] = next;                    
                    mass[at++] = weights[neighbors[others]];
                }

            for (others = next; weights[ancestors[others]]; weights[others = ancestors[others]] -= weights[next]);
            if (others != next) {                
                centroids[history[at] = ancestors[next]] = next;
                mass[at++] = weights[others];
            }
        }
        memset(offsets, 0, sizeof(offsets));
        for (at = vertex_cnt; at--; *(unsigned long *)&offsets[centroids[at]] += 0x100000001UL);
        for (; ++at < (vertex_cnt >> 1); ((unsigned long *)offsets)[at + 1] += ((unsigned long *)offsets)[at]);    
        for (at = vertex_cnt; at--; forward[--offsets[centroids[at]]] = at);                    
    } 

    for (at = forward[(tail = vertex_cnt) - 1]; at != vertex_cnt; at = next) {
        next = ancestors[at];
        ancestors[at] = tail;
        tail = at;
    }        
        
    for (at >>= 1; at--; ((unsigned long *)indices)[at] = 0x200000002UL);                    
    *(unsigned long *)indices = 0x200000001UL;
    for (*(unsigned long *)&indices[(at = vertex_cnt) - 1] = 0x100000002UL; at--; 
        *(unsigned long *)&indices[ancestors[at]] += 0x100000001UL);
    for (; ++at < (vertex_cnt >> 1); ((unsigned long *)indices)[at + 1] += ((unsigned long *)indices)[at]);    
    for (at = vertex_cnt; at--; neighbors[--indices[ancestors[at]]] = at);
    for (; ++at < vertex_cnt; neighbors[--indices[at]] = ancestors[at]);    
    indices[at + 1] = at << 1;
    
    unsigned                 
        ordered[vertex_cnt << 1],
        ranks[vertex_cnt << 1],
        sums[vertex_cnt << 1],
        deltas[2][vertex_cnt],
        seen[((vertex_cnt + 1) >> 5) + 1];

    unsigned long         
        total = 0,
        max[2],
        (*dists)[2][vertex_cnt << 1] = malloc(sizeof(dists[0]));

    memset(seen, 0, sizeof(seen));    
    inv(seen, at);    
    for (history[0] = forward[at - 1], at = 1; at--; ) {                           
        inv(seen, history[at]);                
        dists[0][0][vertex_cnt + history[at]] = (dists[0][1][vertex_cnt + history[at]] = (max[0] = (max[1] = 0UL)));
        for (history[tail = vertex_cnt - 1] = history[next = at]; tail < vertex_cnt; next++) 
            for (others = indices[(history[next] = history[tail++]) + 1]; others-- > indices[history[next]]; )
                if (have(seen, neighbors[others]) == 0) {
                    inv(seen, neighbors[others]);                    
                    weights[history[--tail] = neighbors[others]] = 1;
                    ordered[history[tail]] = history[next];

                    dists[0][0][vertex_cnt + history[tail]] = dists[0][0][vertex_cnt + history[next]] 
                        + delta(cords[0][history[next]], cords[0][history[tail]]);
                    dists[0][1][vertex_cnt + history[tail]] = dists[0][1][vertex_cnt + history[next]] 
                        + delta(cords[1][history[next]], cords[1][history[tail]]);

                    if (max[0] < dists[0][0][vertex_cnt + history[tail]])
                        max[0] = dists[0][0][vertex_cnt + history[tail]];                        
                    if (max[1] < dists[0][1][vertex_cnt + history[tail]])
                        max[1] = dists[0][1][vertex_cnt + history[tail]];
                }       
        if ((max[0] << 1) <= limits[0] && (max[1] << 1) <= limits[1])
            continue ;
        
        for (weights[history[at]] = 1; --next > at; inv(seen, history[next]))
            weights[ordered[history[next]]] += weights[history[next]];                    

        ranks[history[next++]] = 0;
        for (tail = 1, others = next; others < (at + weights[history[at]]); )
            for (next += weights[history[next]], max[0] = tail; others < next; )
                if (dists[0][0][vertex_cnt + history[others]] > limits[0] 
                 || dists[0][1][vertex_cnt + history[others]] > limits[1]) { 
                    total += (max[0] + ((at + weights[history[at]]) - next)) * weights[history[others]];
                    others += weights[history[others]];
                } else {                                                                           
                    ancestors[ranks[history[others]] = tail] = ranks[ordered[history[others]]];                    
                    dists[0][0][tail] = dists[0][0][vertex_cnt + history[others]];
                    dists[0][1][tail++] = dists[0][1][vertex_cnt + history[others++]];                                        
                }

        for (others = tail >> 1; others--; ((unsigned long *)weights)[others] = 0x100000001UL);
        for (weights[(others = tail) - 1] = 1; --others; weights[ancestors[others]] += weights[others]) {
            dists[0][0][tail + others] = limits[0] - dists[0][0][others];
            dists[0][1][tail + others] = limits[1] - dists[0][1][others];

            ordered[others - 1] = others;
            ordered[tail + others - 2] = tail + others;
        }                
        
        others = (tail - 1) << 1;                
        for (ascending_stbl(others, dists[0][1], ordered); others--; ranks[ordered[others]] = others);                                
        for (; ++others < (tail - 1); ordered[others] = others + 1) 
            ordered[tail + others - 1] = tail + others + 1;            
                
        ascending_stbl((others <<= 1), dists[0][0], ordered);                          
        memset(sums, 0, others * sizeof(sums[0]));
        for (tail = 0; tail < others; tail++)
            if (ordered[tail] > weights[0]) {
                deltas[0][ordered[tail] -= weights[0]] = 0;
                for (next = ranks[ordered[tail] + weights[0]]; next != 0xFFFFFFFFU; next = (next & (next + 1)) - 1)
                    deltas[0][ordered[tail]] += sums[next];
                ordered[tail] += weights[0];
            } else                
                for (next = ranks[ordered[tail]]; next < others; next |= next + 1)
                    sums[next]++;                

        unsigned long sum = 0;
        deltas[0][0] = weights[0] - 1;        
        for (others = 1; others < weights[0]; ) {
            for (tail = weights[others]; tail--; ordered[tail] = others + tail) 
                ordered[weights[others] + tail] = weights[0] + others + tail;            
                        
            tail = (weights[others] << 1);
            for (ascending_stbl(tail, dists[0][1], ordered); tail--; ranks[ordered[tail]] = tail);

            for (tail = weights[others]; tail--; ordered[tail] = others + tail) 
                ordered[weights[others] + tail] = weights[0] + others + tail;
            ascending_stbl(weights[others] << 1, dists[0][0], ordered);

            memset(sums, 0, (weights[others] << 1) * sizeof(sums[0]));
            for (tail = 0; tail < (weights[others] << 1); tail++)
                if (ordered[tail] > weights[0]) {                     
                    deltas[1][ordered[tail] -= weights[0]] = 0;
                    for (next = ranks[ordered[tail] + weights[0]]; next != 0xFFFFFFFFU; next = (next & (next + 1)) - 1)
                        deltas[1][ordered[tail]] += sums[next];
                    ordered[tail] += weights[0];
                } else                     
                    for (next = ranks[ordered[tail]]; next < (weights[others] << 1); next |= next + 1)
                        sums[next]++;                    
            
            deltas[1][0] = weights[others];       
            for (tail = others + (tail >> 1); others < tail; others++)
                sum += weights[others] * (unsigned long)(
                    (deltas[0][ancestors[others]] - deltas[0][others])
                  - (deltas[1][ancestors[others]] - deltas[1][others])
                );            
        }
        total += sum >> 1;

        others = offsets[history[at] + 1] - offsets[history[at]];
        memcpy(&history[at], &forward[offsets[history[at]]], others * sizeof(history[0]));
        at += others;                
    }
    printf("%lu", total); 
    
    free(dists);    
    return 0;
}