By Daniel L. (8th Grade)
You can do BFS. 2 nodes i and j are connected by an edge if Bessie can give pie i to Elsie given that she received pie j. You can push all of bessie’s pies with value 0 for elsie and all of elsie’s pies with value 0 for bessie. There are many edges, so brute force is too slow. Instead, we put all of Bessie’s pies into a set and all of Elsie’s pies into a set. When you visit a node, you remove it from the set so that you don’t visit it twice.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen(“piepie.in”,”r”,stdin);
freopen(“piepie.out”,”w”,stdout);
int n,d;
cin >> n >> d;
vector<pair<int,int>> arr(2*n);
set<pair<int,int>> s1,s2;
queue<pair<int,int>> q;
vector<int> answer(2*n,1000000000);
for (int i = 0; i < 2*n; i++) {
cin >> arr[i].first >> arr[i].second;
if (arr[i].first == 0 && i >= n || arr[i].second == 0 && i < n) {
q.push({1,i});
}
if (i < n) {
s1.insert({arr[i].second,i});
}
else {
s2.insert({arr[i].first,i});
}
}
while (!q.empty()) {
int dist = q.front().first;
int node = q.front().second;
q.pop();
answer[node] = min(answer[node],dist);
if (node < n) {
while (s2.size() && s2.upper_bound({arr[node].first,1000000000}) != s2.begin() && (*(–s2.upper_bound({arr[node].first,1000000000}))).first >= arr[node].first-d) {
int a = (*(–s2.upper_bound({arr[node].first,1000000000}))).second;
q.push({dist+1,a});
s2.erase(–s2.upper_bound({arr[node].first,1000000000}));
}
}
else {
while (s1.size() && s1.upper_bound({arr[node].second,1000000000}) != s1.begin() && (*(–s1.upper_bound({arr[node].second,1000000000}))).first >= arr[node].second-d) {
int a = (*(–s1.upper_bound({arr[node].second,1000000000}))).second;
q.push({dist+1,a});
s1.erase(–s1.upper_bound({arr[node].second,1000000000}));
}
}
}
for (int i = 0; i < n; i++) {
if (answer[i] == 1000000000) {
answer[i] = -1;
}
}
for (int i = 0; i < n; i++) {
cout << answer[i] << “\n”;
}
}
