제출 #257016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
257016		rama_pang	Park (BOI16_park)	C++14	100 / 100	1014 ms	33724 KiB

park

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

class DisjointSet {
 public:
  vector<int> p;
  DisjointSet() {}
  DisjointSet(int sz) : p(sz) {
    iota(begin(p), end(p), 0);
  }
  void Clear() {
    iota(begin(p), end(p), 0);
  }
  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }
  int Unite(int x, int y) {
    x = Find(x), y = Find(y);
    if (x != y) {
      p[x] = y;
      return 1;
    }
    return 0;
  }
  bool SameSet(int x, int y) {
    return Find(x) == Find(y);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, Q, H, W;
  cin >> N >> Q >> W >> H;
  vector<long long> X(N), Y(N), R(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i] >> R[i];
  }

  vector<long long> blocks(6, 1e18);
  // blocks[0] = cover left to down
  // blocks[1] = cover down to right
  // blocks[2] = cover right to up
  // blocks[3] = cover up to left
  // blocks[4] = cover left to right
  // blocks[5] = cover up to down

  auto GetSide = [&](long long x, long long y) {
    if (x < 0) return N + 0;
    if (y < 0) return N + 1;
    if (x > W) return N + 2;
    if (y > H) return N + 3;
    return -1;
  };

  vector<pair<long long, pair<int, int>>> edges;
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      long long lo = 0, hi = 1e9;
      while (lo < hi) {
        long long md = (lo + hi) / 2;
        if ((X[i] - X[j]) * (X[i] - X[j]) + 
            (Y[i] - Y[j]) * (Y[i] - Y[j]) < 
            (R[i] + R[j] + 2ll * md) * (R[i] + R[j] + 2ll * md)) {
          hi = md;
        } else {
          lo = md + 1;
        }
      }
      edges.push_back({lo, {i, j}});
    }
  }
  for (int i = 0; i < N; i++) {
    {
      long long lo = 0, hi = 1e9;
      while (lo < hi) {
        long long md = (lo + hi) / 2;
        if (GetSide(X[i] - 2ll * md - R[i], Y[i]) != -1) {
          hi = md;
        } else {
          lo = md + 1;
        }
      }
      edges.push_back({lo, {i, GetSide(X[i] - 2ll * lo - R[i], Y[i])}});
    }
    {
      long long lo = 0, hi = 1e9;
      while (lo < hi) {
        long long md = (lo + hi) / 2;
        if (GetSide(X[i] + 2ll * md + R[i], Y[i]) != -1) {
          hi = md;
        } else {
          lo = md + 1;
        }
      }
      edges.push_back({lo, {i, GetSide(X[i] + 2ll * lo + R[i], Y[i])}});
    }
    {
      long long lo = 0, hi = 1e9;
      while (lo < hi) {
        long long md = (lo + hi) / 2;
        if (GetSide(X[i], Y[i] - 2ll * md - R[i]) != -1) {
          hi = md;
        } else {
          lo = md + 1;
        }
      }
      edges.push_back({lo, {i, GetSide(X[i], Y[i] - 2ll * lo - R[i])}});
    }
    {
      long long lo = 0, hi = 1e9;
      while (lo < hi) {
        long long md = (lo + hi) / 2;
        if (GetSide(X[i], Y[i] + 2ll * md + R[i]) != -1) {
          hi = md;
        } else {
          lo = md + 1;
        }
      }
      edges.push_back({lo, {i, GetSide(X[i], Y[i] + 2ll * lo + R[i])}});
    }
  }

  DisjointSet D(N + 4);
  sort(begin(edges), end(edges));
  for (auto e : edges) {
    D.Unite(e.second.first, e.second.second);
    if (D.SameSet(N + 0, N + 1)) blocks[0] = min(blocks[0], e.first);
    if (D.SameSet(N + 1, N + 2)) blocks[1] = min(blocks[1], e.first);
    if (D.SameSet(N + 2, N + 3)) blocks[2] = min(blocks[2], e.first);
    if (D.SameSet(N + 3, N + 0)) blocks[3] = min(blocks[3], e.first);
    if (D.SameSet(N + 0, N + 2)) blocks[4] = min(blocks[4], e.first);
    if (D.SameSet(N + 1, N + 3)) blocks[5] = min(blocks[5], e.first);    
  }

  while (Q--) {
    int r, e;
    cin >> r >> e;
    e--;
    string ans;
    for (int i = 0; i < 4; i++) {
      long long b = min(blocks[e], blocks[i]);
      if (((e == 0 || e == 1) && (i == 2 || i == 3)) || ((i == 0 || i == 1) && (e == 2 || e == 3))) {
        b = min(b, blocks[4]);
      }
      if (((e == 0 || e == 3) && (i == 1 || i == 2)) || ((i == 0 || i == 3) && (e == 1 || e == 2))) {
        b = min(b, blocks[5]);
      }
      if (e == i || r < b) {
        ans.push_back('1' + i);
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42