This problem can be reframed as a shortest-path problem. We consider each pie to be a node, and a directed edge between nodes $A$ and $B$ to exist if Bessie can gift pie $B$ to Elsie after receiving pie $A$ (or likewise for Elsie to Bessie). Under this formulation, we are given $2N$ "starting nodes" and must determine, for each such node, the shortest path to a valid "ending node".

We cannot simply use all-pairs shortest paths to solve this problem, as such algorithms are too slow for $N \leq 10^5$. However, we can take advantage of the fact that all paths have weight $1$, and perform the search using a BFS from multiple source nodes. This can be done simply by adding all source nodes to the queue at the beginning of the algorithm.

Normally, this algorithm would take $O(N)$, but we also need to efficiently find, for various given $k$, the set of nodes that have tastiness value between $k$ and $k + D$. This can be done using binary search after sorting both Bessie's and Elsie's list of pies by how tasty they consider them to be. This makes our overall running time $O(N \lg N)$, which is still plenty fast enough to receive full credit.

Here's Dhruv's solution. He uses C++'s $\texttt{multiset}$ to perform binary searches:

#include <iostream> #include <algorithm> #include <set> using namespace std; #define MAXN 100000 #define INF 1000000000 int N,D; int A[2*MAXN]; int B[2*MAXN]; int dist[2*MAXN]; struct cmpA { bool operator()(int a,int b) const { return B[a]<B[b]; } }; struct cmpB { bool operator()(int a,int b) const { return A[a]<A[b]; } }; multiset<int,cmpA> sA; multiset<int,cmpB> sB; int que[2*MAXN]; int cur,len; int main() { cin >> N >> D; for(int i=0;i<2*N;i++) { cin >> A[i] >> B[i]; A[i] = -A[i], B[i] = -B[i]; dist[i] = -1; } for(int i=0;i<N;i++) { if(B[i]==0) que[len++] = i, dist[i] = 1; else sA.insert(i); if(A[N+i]==0) que[len++] = N+i, dist[N+i] = 1; else sB.insert(N+i); } multiset<int,cmpA>::iterator itA; multiset<int,cmpB>::iterator itB; while(cur < len) { int i = que[cur]; if(i < N) { while(1) { itB = sB.lower_bound(i); if(itB == sB.end() || A[*itB] > A[i]+D) break; dist[*itB] = dist[i] + 1; que[len++] = *itB; sB.erase(itB); } } else { while(1) { itA = sA.lower_bound(i); if(itA == sA.end() || B[*itA] > B[i]+D) break; dist[*itA] = dist[i] + 1; que[len++] = *itA; sA.erase(itA); } } cur++; } for(int i=0;i<N;i++) cout << dist[i] << '\n'; }