Overview

In this problem, we want to find the minimum number of jumps to reach the destination \((0,W)\) from the starting point \((0,0)\) by successively jumping to debris within distance \(D\). The essence of the problem is to perform a BFS (Breadth-First Search) on a massive graph whose edges are implicitly defined by the geometric condition “within distance \(D\)”, fast enough to handle \(N \le 10^5\).

Analysis

Graph Formulation

Let the vertices be the mothership \((0,0)\), each piece of debris \((x_i,y_i)\), and the station \((0,W)\), with unweighted edges (weight \(1\)) between any two points within distance \(D\). However, a direct jump from the mothership to the station is forbidden (it must visit at least one piece of debris).

Since all edge weights are \(1\), the minimum number of jumps can be found using BFS.

Issues with the Naive Approach

A naive approach would compute the distance between all pairs of vertices to construct an adjacency list. In the worst case, the number of edges is \(O(N^2) = 10^{10}\), which will exceed both the time and memory limits by a large margin.

For instance, if all debris is densely packed within a small area of radius \(D\), there would truly be \(\Theta(N^2)\) edges. Therefore, we must devise a method that does not construct an explicit adjacency list.

Key Insight: Each Vertex Is Visited Only Once in BFS

An essential property of BFS is that once the shortest distance to a vertex is determined, it is never updated again. In other words, when expanding from vertex \(u\), all we need is:

“All unvisited debris within distance \(D\) from \(u\).”

Repeatedly iterating over already visited points is completely redundant.

Thus, we adopt the following strategy:

• Maintain a data structure that spatially partitions the set of points (a kd-tree).
• Perform circular range queries: “enumerate all points within radius \(D\) from a given point.”
• Delete points from the data structure once they are enumerated and marked as visited.

With this approach, each point is extracted at most once throughout the entire process, bounding the total cost of extracting points to \(O(N)\). The only remaining overhead comes from traversing regions where no alive points are found, which can be kept practically fast by pruning subtrees in the kd-tree where the number of alive points is \(0\).

This is a classic technique: “performing BFS with neighborhood search supporting deletions” (a similar approach can also be implemented using grid partitioning or segment trees with sets).

Algorithm

1. Build a kd-tree over the array of debris coordinates.

   • Each node stores the point range \([l, r)\) it is responsible for, the bounding box of the region (minimum and maximum coordinates of \(x\) and \(y\)), and the number of alive points alive.
   • For splitting, choose the axis (\(x\) or \(y\)) with the larger spread and partition at the median using nth_element (group about \(16\) points into leaf nodes).

2. Circular range query query(point q):

   • If the node has alive == 0, return immediately (skip blocks of already deleted points).
   • If the minimum distance from \(q\) to the node’s bounding box exceeds \(D\), return immediately (prune).
   • If it is a leaf, linearly scan the unvisited points in its range, append points with distance \(\le D\) to the result list, and decrement alive.
   • If it is an internal node, recursively visit both children, then recompute alive as the sum of its children’s counts.

3. BFS:

   • First, query from \((0,0)\). For all retrieved points, set their distance to \(1\) and push them into the queue (they are simultaneously marked as deleted from the kd-tree).
   • Pop \(u\) from the queue and perform a query at \(u\)’s coordinates. For all newly found points, set their distance to \(\mathrm{dist}(u)+1\) and push them into the queue.
   • Repeat until the queue is empty.

4. Calculating the answer:

   • For each debris \(i\), if \(\mathrm{dist}(i)\) has been determined and the distance from \(i\) to \((0,W)\) is at most \(D\), then \(\mathrm{dist}(i)+1\) is a candidate answer.
   • Output the minimum among all candidates. If there are no valid candidates, output -1.
   • Enforcing that we always jump to the goal via at least one piece of debris automatically satisfies the constraint that a direct jump from the mothership to the station is forbidden.

Complexity

We perform \(N+1\) circular queries with deletions on the kd-tree, but the total number of extracted points across all queries is \(O(N)\). A practical estimate including traversal overhead is as follows:

• Time Complexity: \(O(N \log N)\) for tree construction, and roughly \(O(N \sqrt{N})\) on average for the entire BFS (while the theoretical worst case could be higher, pruning via alive makes it sufficiently fast for \(N = 10^5\)).
• Space Complexity: \(O(N)\)

Implementation Notes

• Always compare squared distances: Using sqrt incurs both precision issues and performance penalties. Compare using \(dx^2+dy^2 \le D^2\).

• Beware of integer overflow: Since \(|x| \le 10^9\), \(W \le 10^9\), and \(D \le 10^9\), \(dx^2\) can reach up to around \(4\times10^{18}\). Perform calculations using 64-bit integers (long long). Note that \(D^2 \le 10^{18}\) also safely fits within a standard signed 64-bit integer.

• Managing alive: When points are extracted at a leaf, decrement that leaf’s alive count, and update each internal node’s alive as the sum of its children when returning from recursion. Without this, fully visited regions would be traversed repeatedly, resulting in TLE.

• Minimum distance between a bounding box and a point: For each axis, add only the distance by which \(q\) lies outside the interval (\(0\) if it is inside):

  
  dx = max(0, minx - qx, qx - maxx)
  dy = max(0, miny - qy, qy - maxy)
  

• Leaf size: Creating a separate leaf node for each individual point increases the total number of nodes and the recursion overhead. Grouping around \(16\) points per leaf improves the constant factor significantly.

• Fast I/O: Since there are \(N = 10^5\) lines of input, using fast custom integer reading via getchar_unlocked or scanf is recommended.

• Checking reachability: If no debris that can reach \((0,W)\) is visited after the BFS finishes, output -1. Since the \(y\)-coordinate of the debris satisfies \(1 \le y_i \le W-1\), debris will never overlap with the station’s coordinates.

  Source Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node { ll minx, maxx, miny, maxy; int l, r, lc, rc, alive; };
static vector<Node> tr;
static vector<pair<ll,ll>> pts;
static vector<int> dst;
static ll D2;
static vector<int> found_;

int build(int l, int r) {
    int id = (int)tr.size();
    tr.push_back(Node());
    ll mnx = LLONG_MAX, mxx = LLONG_MIN, mny = LLONG_MAX, mxy = LLONG_MIN;
    for (int i = l; i < r; i++) {
        mnx = min(mnx, pts[i].first); mxx = max(mxx, pts[i].first);
        mny = min(mny, pts[i].second); mxy = max(mxy, pts[i].second);
    }
    tr[id].minx = mnx; tr[id].maxx = mxx; tr[id].miny = mny; tr[id].maxy = mxy;
    tr[id].l = l; tr[id].r = r; tr[id].alive = r - l; tr[id].lc = tr[id].rc = -1;
    if (r - l <= 16) return id;
    int m = (l + r) / 2;
    if (mxx - mnx >= mxy - mny)
        nth_element(pts.begin()+l, pts.begin()+m, pts.begin()+r,
            [](const pair<ll,ll>&a, const pair<ll,ll>&b){ return a.first < b.first; });
    else
        nth_element(pts.begin()+l, pts.begin()+m, pts.begin()+r,
            [](const pair<ll,ll>&a, const pair<ll,ll>&b){ return a.second < b.second; });
    int lc = build(l, m);
    int rc = build(m, r);
    tr[id].lc = lc; tr[id].rc = rc;
    return id;
}

void query(int id, ll qx, ll qy) {
    Node &n = tr[id];
    if (n.alive == 0) return;
    ll dx = 0, dy = 0;
    if (qx < n.minx) dx = n.minx - qx; else if (qx > n.maxx) dx = qx - n.maxx;
    if (qy < n.miny) dy = n.miny - qy; else if (qy > n.maxy) dy = qy - n.maxy;
    if (dx*dx + dy*dy > D2) return;
    if (n.lc < 0) {
        int cnt = 0;
        for (int i = n.l; i < n.r; i++) {
            if (dst[i] != -1) continue;
            ll ddx = pts[i].first - qx, ddy = pts[i].second - qy;
            if (ddx*ddx + ddy*ddy <= D2) { found_.push_back(i); cnt++; }
        }
        n.alive -= cnt;
        return;
    }
    int lc = n.lc, rc = n.rc;
    query(lc, qx, qy);
    query(rc, qx, qy);
    tr[id].alive = tr[lc].alive + tr[rc].alive;
}

static inline int readInt() {
    int c = getchar_unlocked();
    while (c != '-' && (c < '0' || c > '9')) c = getchar_unlocked();
    int sgn = 1;
    if (c == '-') { sgn = -1; c = getchar_unlocked(); }
    long long x = 0;
    while (c >= '0' && c <= '9') { x = x*10 + (c - '0'); c = getchar_unlocked(); }
    return (int)(x * sgn);
}

int main() {
    int N = readInt();
    ll W = readInt();
    ll D = readInt();
    D2 = D * D;
    pts.resize(N);
    for (int i = 0; i < N; i++) {
        ll x = readInt();
        ll y = readInt();
        pts[i] = {x, y};
    }
    tr.reserve(2 * (N / 8 + 4));
    int root = build(0, N);
    dst.assign(N, -1);
    found_.reserve(N);

    vector<int> q;
    q.reserve(N);
    found_.clear();
    query(root, 0, 0);
    for (int p : found_) { dst[p] = 1; q.push_back(p); }

    size_t head = 0;
    while (head < q.size()) {
        int u = q[head++];
        found_.clear();
        query(root, pts[u].first, pts[u].second);
        int du = dst[u];
        for (int p : found_) { dst[p] = du + 1; q.push_back(p); }
    }

    long long ans = LLONG_MAX;
    for (int i = 0; i < N; i++) {
        if (dst[i] < 0) continue;
        ll dx = pts[i].first - 0;
        ll dy = pts[i].second - W;
        if (dx*dx + dy*dy <= D2) ans = min(ans, (long long)dst[i] + 1);
    }
    if (ans == LLONG_MAX) printf("-1\n");
    else printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude5opus-high.