题解

这个问题可以重新构造成一个最短路径问题。我们将每个馅饼视为一个节点，如果 Bessie 可以在收到馅饼 A 后将馅饼 B 送给 Elsie（或者同样地 Elsie 送给 Bessie），则存在从节点 A 到节点 B 的有向边。在这种表述下，我们有 2N 个“起始节点”，必须确定对于每个这样的节点，到达有效“结束节点”的最短路径。

显然，我们不能简单地使用全对最短路径算法来解决这个问题，因为这种算法对于 N≤105 来说太慢了。然而，我们可以利用所有路径的权重都为 1 的事实，从多个源节点开始使用 BFS 进行搜索。这可以通过在算法开始时将所有源节点添加到队列中来简单实现。

通常情况下，这个算法需要 O(N) 时间，但我们还需要高效地找到对于给定的 k，那些具有口感值在 k 和 k+D 之间的节点集合。在将 Bessie 和 Elsie 的馅饼列表按照它们的美味程度排序后，可以使用二分搜索来完成这一点。这使得我们的总运行时间为 O(NlgN)，这仍然足够快以获得完整的分数。

#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';
}