제출 #973341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
973341		jakobrs	Park (BOI16_park)	C++17	0 / 100	388 ms	67516 KiB

park

#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <variant>
#include <vector>

template <typename... T> struct overloaded : public T... {
  using T::operator()...;
};

template <typename... T> overloaded(T...) -> overloaded<T...>;
struct Time {
  int64_t integral;
  int64_t rooted;

  template <bool EQ> auto compare(Time rhs) const -> bool {
    /*
      i + sqrt(r) < i1 + sqrt(r1)
      sqrt(r) < id + sqrt(r1)
      r < id^2 + 2 id sqrt(r1) + r1
      r - id^2 - r1 < 2 id sqrt(r1)
      (r - r1 - id^2)^2 < 4 id^2 r1
      // i^2 - r < (i1 + sqrt(r1))(i - sqrt(r))
      //         = i*i1 + i sqrt(r1) - i sqrt(r) + sqrt(r r1)
    */

    using i128 = __int128_t;
    // using i128 = int64_t;

    if (rhs.integral < integral)
      return !rhs.compare<true>(*this);

    auto id = rhs.integral - integral;
    auto lhs_pre_square = rooted - rhs.rooted - id * id;

    // std::cerr << lhs_pre_square << '\n';

    if (lhs_pre_square < 0) {
      return true;
    }

    auto lhs_eval = (i128)lhs_pre_square;
    lhs_eval *= lhs_eval;

    i128 rhs_eval = rhs.rooted;
    rhs_eval *= 4 * id * id;

    // std::cerr << "Comparing " << integral << " + sqrt(" << rooted << ") < "
    //           << rhs.integral << " + sqrt(" << rhs.rooted << ") <==> "
    //           << lhs_eval << " < " << rhs_eval << "\n";
    return lhs_eval < rhs_eval || (EQ && lhs_eval == rhs_eval);
  }

  auto operator<(Time rhs) const -> bool { return this->compare<false>(rhs); }
};

struct UnionFind {
  std::vector<int> parent;

  UnionFind(int n) : parent(n, -1) {}

  auto find(int idx) -> int {
    if (parent[idx] < 0)
      return idx;
    else
      return parent[idx] = find(parent[idx]);
  }

  auto unite(int l, int r) -> bool {
    l = find(l);
    r = find(r);

    if (l == r)
      return false;

    if (-parent[l] < -parent[r])
      std::swap(l, r);

    parent[l] += parent[r];
    parent[r] = l;

    return true;
  }
};

int main() {
  int n, m;
  std::cin >> n >> m;

  int w, h;
  std::cin >> w >> h;

  struct Tree {
    int x, y, r;
  };
  auto trees = std::vector<Tree>(n);

  for (auto &tree : trees)
    std::cin >> tree.x >> tree.y >> tree.r;

  auto answers = std::vector<std::bitset<4>>(m);

  struct Event {
    struct Tree {
      int u, v;
    };
    struct Query {
      int c;
      int id;
    };

    Time time;
    std::variant<Tree, Query> data;

    auto operator<(const Event &rhs) const -> bool {
      return std::pair{time, std::holds_alternative<Query>(data)} <
             std::pair{rhs.time, std::holds_alternative<Query>(rhs.data)};
    }
  };

  auto events = std::vector<Event>{};
  auto left = n + 0;
  auto bottom = n + 1;
  auto right = n + 2;
  auto top = n + 3;
  for (int i = 0; i < trees.size(); i++) {
    for (int j = i + 1; j < trees.size(); j++) {
      // sqrt(dx^2 + dy^2) - r1 - r2
      auto dx = trees[j].x - trees[i].x;
      auto dy = trees[j].y - trees[i].y;
      auto r1 = trees[i].r;
      auto r2 = trees[j].r;

      auto dist = std::sqrt(dx * dx + dy * dy);
      auto time = Time{
          .integral = -r1 - r2,
          .rooted = dx * dx + dy * dy,
      };

      // std::cerr << time.integral << " " << time.rooted << "\n";

      events.push_back(Event{
          .time = time,
          .data = {Event::Tree{i, j}},
      });
    }

    // edges
    auto [x, y, r] = trees[i];
    events.push_back(Event{
        .time = Time{.integral = x - r, .rooted = 0},
        .data = {Event::Tree{i, left}},
    });
    events.push_back(Event{
        .time = Time{.integral = w - x - r, .rooted = 0},
        .data = {Event::Tree{i, right}},
    });
    events.push_back(Event{
        .time = Time{.integral = y - r, .rooted = 0},
        .data = {Event::Tree{i, bottom}},
    });
    events.push_back(Event{
        .time = Time{.integral = h - y - r, .rooted = 0},
        .data = {Event::Tree{i, top}},
    });
  }

  for (int i = 0; i < m; i++) {
    int r, c;
    std::cin >> r >> c;
    events.push_back(Event{
        .time = Time{.integral = 2 * r, .rooted = 0},
        .data = {Event::Query{c - 1, i}},
    });
  }

  std::sort(events.begin(), events.end());

  auto dsu = UnionFind(n + 4);

  for (auto event : events) {
    // std::cerr << event.time.integral << " + sqrt " << event.time.rooted
    //           << " approx "
    //           << (double(event.time.integral) + std::sqrt(event.time.rooted))
    //           << "\n";
    auto visitor = overloaded{
        [&](Event::Tree data) {
          // std::cerr << "Tree " << data.u << " " << data.v << "\n";
          dsu.unite(data.u, data.v);
        },
        [&](Event::Query data) {
          auto [c, i] = data;
          // std::cerr << "Query " << c << " " << i << "\n";

          std::bitset<4> can_reach;
          for (int d = 0; d < 4; d++) {
            can_reach[d] = true;
            for (int x = 0; x < 4; x++) {
              for (int y = 0; y < 4; y++) {
                auto x_between = (c < x && x <= d) || (d < x && x <= c);
                auto y_between = (c < y && y <= d) || (d < y && y <= c);

                if (x_between && !y_between &&
                    dsu.find(n + x) == dsu.find(n + y)) {
                  can_reach[d] = false;
                  goto next;
                }
              }
            }
          next:;
          }

          answers[i] = can_reach;
        }};

    std::visit(visitor, event.data);
  }

  for (auto x : answers) {
    for (int i = 0; i < 4; i++)
      if (x[i])
        std::cout << i + 1;
    std::cout << '\n';
  }
}

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'int main()':
park.cpp:127:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for (int i = 0; i < trees.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~
park.cpp:128:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int j = i + 1; j < trees.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~
park.cpp:135:12: warning: unused variable 'dist' [-Wunused-variable]
  135 |       auto dist = std::sqrt(dx * dx + dy * dy);
      |            ^~~~

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