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("DOIT\n");
//FO(i,0,sz(p)) printf("%lld,%lld\n", 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 %lld\n", 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("%lld\n", 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;
}
0 Comments