BOJ 15457 - A Pie for a Pie

BOJ 15457 - A Pie for a Pie

BFS 임은 어렵지 않게 추측할 수 있지만 구현에서 애를 먹었다.

$2N$개의 정점이 있다고 하자. $1 \to N$ 은 $b_i$ 순으로 정렬하고 $N+1 \to 2N$은 $a_i$ 순으로 정렬하자.

$1 \to N$ 의 정점 중 $b_i=0$ 인 것이 있다면 이것의 최단거리를 $1$로 잡고, 반대쪽은 $a_i=0$ 인 걸 1로 잡는다.

일반성을 잃지않고 $1 \to N$ 의 정점이라고 하자.

그럼 Bessie -> Elsie 에게 주었다는 뜻이므로 이전에 Bessie가 받은 인덱스를 $j \quad (N+1 \le j \le 2N)$ 이라 할 때, $a_i-D \le a_j \le a_i$ 여야 한다.

이러한 $j$의 후보들을 모두 순회하며 최단경로를 갱신해준다.

여기서 그럼 간선이 $O(N^2)$ 가 되기 때문에 시간초과가 날 수 있는데, 이미 방문한 정점들을 집합에서 삭제해주는 방식으로 $O(N \log N)$ 으로 모든 정점의 최단거리를 갱신할 수 있게 처리해야 한다.

const int inf = 2e9;
void solve() {
   int n, d;
   cin >> n >> d;
   vector<array<int, 3>> a(n), b(n);
   for (int i = 0; i < n; i++) {
      cin >> a[i][0] >> a[i][1];
      a[i][2] = i;
   }
   for (int i = 0; i < n; i++) {
      cin >> b[i][0] >> b[i][1];
      b[i][2] = i + n;
   }
   sort(all(a), [&](auto &a, auto &b) { return a[1] < b[1]; });
   sort(all(b), [&](auto &a, auto &b) { return a[0] < b[0]; });
   vi dist(n * 2, 2e9);
   queue<int> q;
   set<int> remain;
   for (int i = 0; i < 2 * n; i++) remain.insert(i);
   for (int i = 0; i < n; i++) {
      if (a[i][1] == 0) {
         dist[i] = 1;
         q.push(i);
         remain.erase(i);
      }
      if (b[i][0] == 0) {
         dist[i + n] = 1;
         q.push(i + n);
         remain.erase(i + n);
      }
   }

   while (sz(q)) {
      auto cur = q.front();
      q.pop();

      // Bessie -> Elsie 였다면
      if (cur < n) {
         array<int, 3> st = {a[cur][0] - d, -1};
         array<int, 3> et = {a[cur][0], inf};
         int s = ubi(b, st), e = ubi(b, et) - 1;
         int ss = s;

         auto it = remain.lower_bound(s + n);
         vi cand;
         while (it != remain.end() && *it <= e + n) {
            cand.pb(*it);
            it++;
         }
         for (int c: cand) {
            dist[c] = dist[cur] + 1;
            q.push(c);
            remain.erase(c);
         }
      } else {
         // Elsie -> Besise 였다면
         int s = n, e = -1;
         {
            int l = 0, r = n - 1;
            while (l <= r) {
               int m = l + r >> 1;
               if (a[m][1] >= b[cur - n][1] - d) s = m, r = m - 1;
               else l = m + 1;
            }
         }
         {
            int l = 0, r = n - 1;
            while (l <= r) {
               int m = l + r >> 1;
               if (a[m][1] <= b[cur - n][1]) e = m, l = m + 1;
               else r = m - 1;
            }
         }
         auto it = remain.lower_bound(s);
         vi cand;
         while (it != remain.end() && *it <= e) {
            cand.pb(*it);
            it++;
         }
         for (int c: cand) {
            dist[c] = dist[cur] + 1;
            q.push(c);
            remain.erase(c);
         }
      }
   }
   vi ans(n);
   for (int i = 0; i < n; i++) {
      if (dist[i] == 2e9) ans[a[i][2]] = -1;
      else ans[a[i][2]] = dist[i];
   }
   for (int i = 0; i < n; i++) cout << ans[i] << endl;
}