제출 #831222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831222		badont	Park (BOI16_park)	C++17	100 / 100	603 ms	57748 KiB

park

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

// clang-format off
template <typename T, typename = void> struct is_iterable : false_type {};template <typename T>struct is_iterable<    T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>>    : true_type {};template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value,ostream &>::type operator<<(ostream &cout, T const &v);template <typename A, typename B>ostream &operator<<(ostream &cout, pair<A, B> const &p) {  return cout << "(" << p.first << ", " << p.second << ")";}template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value, ostream &>::type operator<<(ostream &cout, T const &v) {  cout << "[";  for (auto it = v.begin(); it != v.end();) {cout << *it; if (++it != v.end()) cout << ", ";  } return cout << "]";}

#ifdef LOCAL
  void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
  #define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
  #define debug(...) "zzz"
#endif
// clang-format on

using ll = long long;
using ld = long double;
using pii = pair<ll, ll>;

#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

struct DSU {
  ll n;
  vector<ll> par, sz;

  DSU(ll n) : n(n), par(n), sz(n, 1) { iota(all(par), 0); }

  ll fnd(ll g) {
    if (g == par[g])
      return g;
    return par[g] = fnd(par[g]);
  }

  bool onion(ll a, ll b) {
    a = fnd(a), b = fnd(b);
    if (a == b) {
      return false;
    }
    if (sz[a] > sz[b])
      swap(a, b);
    sz[b] += sz[a];
    par[a] = b;
    return true;
  }
};

void solve() {
  // open
  ll n, m;
  cin >> n >> m;

  ll w, h;
  cin >> w >> h;

  const ll B = 4;
  vector<array<ll, 3>> a(n);

  for (auto &[radius, x, y] : a) {
    cin >> x >> y >> radius;
  }

  vector<array<ll, 2>> b(m);
  for (auto &[r, l] : b) {
    cin >> r >> l;
    l--;
  }

  debug(a, b);

  vector<ll> b_process(m);
  iota(all(b_process), 0);

  sort(all(b_process),
       [&](const ll &x, const ll &y) { return b[x][0] < b[y][0]; });

  vector<array<ll, 3>> edges;
  constexpr ld EPS = 1e-9;
  for (int i = 0; i < n; i++) {
    const auto &[radius, x, y] = a[i];
    for (int j = 0; j < i; j++) {
      const auto &[r2, x2, y2] = a[j];
      ld central_dist = sqrt((x2 - x) * (x2 - x) + (y2 - y) * (y2 - y));
      ld edge_dist = central_dist - radius - r2;

      edges.pb({(ll)ceil(edge_dist + EPS), i + B, j + B});
    }

    //     3
    //  0 [] 2
    //     1
    edges.pb({x + 1 - radius, 0, i + B});
    edges.pb({y + 1 - radius, 1, i + B});
    edges.pb({w - x + 1 - radius, 2, i + B});
    edges.pb({h - y + 1 - radius, 3, i + B});
  }

  sort(all(edges));
  ll nxt_edge_ptr = 0;

  //    3  2
  //    []
  //   0  1

  //     3
  //  0 [] 2
  //     1

  // 0 : 1, 3, 2
  // 1 : 0, 2, 3
  // 2 : 3, 1, 0
  // 3 : 2, 0, 1

  vector seq = vector{
      vector<int>{1, 3, 2},
      vector<int>{0, 2, 3},
      vector<int>{3, 1, 0},
      vector<int>{2, 0, 1},
  };

  DSU dsu(n + B);
  vector<vector<ll>> fin(m);
  for (const auto &idx : b_process) {
    const auto &[rad, entrance] = b[idx];

    while (nxt_edge_ptr < edges.size()) {
      const auto &[weight, x, y] = edges[nxt_edge_ptr];
      if (weight > 2LL * rad)
        break;

      dsu.onion(x, y);
      debug(x, y, rad, weight, idx);
      nxt_edge_ptr++;
    }

    bool h_block = dsu.fnd(0) == dsu.fnd(2);
    bool v_block = dsu.fnd(1) == dsu.fnd(3);

    vector<bool> blocked(B);
    for (int i = 0; i < B; i++) {
      blocked[i] = dsu.fnd(i) == dsu.fnd((i + 1) % B);
    }

    debug(blocked, v_block, h_block);

    vector<ll> ans = {entrance};
    auto &r = seq[entrance];
    if (!v_block and !blocked[r[0]] and !blocked[entrance]) {
      ans.pb(r[0]);
    }
    if (!h_block and !blocked[r[1]] and !blocked[entrance]) {
      ans.pb(r[1]);
    }
    if (!h_block and !v_block and !blocked[r[2]] and !blocked[entrance]) {
      ans.pb(r[2]);
    }
    sort(all(ans));
    fin[idx] = ans;
  }

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < fin[i].size(); j++) {
      cout << fin[i][j] + 1;
    }
    cout << "\n";
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(false);

  ll T = 1;
  // cin >> T;
  for (int t = 0; t < T; t++)
    solve();

  cout.flush();
  return 0;
}

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

park.cpp: In function 'void solve()':
park.cpp:11:22: warning: statement has no effect [-Wunused-value]
   11 |   #define debug(...) "zzz"
      |                      ^~~~~
park.cpp:71:3: note: in expansion of macro 'debug'
   71 |   debug(a, b);
      |   ^~~~~
park.cpp:128:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     while (nxt_edge_ptr < edges.size()) {
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~
park.cpp:11:22: warning: statement has no effect [-Wunused-value]
   11 |   #define debug(...) "zzz"
      |                      ^~~~~
park.cpp:134:7: note: in expansion of macro 'debug'
  134 |       debug(x, y, rad, weight, idx);
      |       ^~~~~
park.cpp:11:22: warning: statement has no effect [-Wunused-value]
   11 |   #define debug(...) "zzz"
      |                      ^~~~~
park.cpp:146:5: note: in expansion of macro 'debug'
  146 |     debug(blocked, v_block, h_block);
      |     ^~~~~
park.cpp:164:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for (int j = 0; j < fin[i].size(); j++) {
      |                     ~~^~~~~~~~~~~~~~~

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