oj.uz

Submission #831222

# Submission time Handle Problem Language Result Execution time Memory
831222 2023-08-20T00:08:11 Z badont Park (BOI16_park) C++17
100 / 100
 603 ms 57748 KB 
#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;
}

Compilation message

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 49688 KB Output is correct
2 Correct 529 ms 49732 KB Output is correct
3 Correct 538 ms 49792 KB Output is correct
4 Correct 534 ms 49828 KB Output is correct
5 Correct 534 ms 49704 KB Output is correct
6 Correct 584 ms 49724 KB Output is correct
7 Correct 524 ms 49792 KB Output is correct
8 Correct 517 ms 49784 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 10480 KB Output is correct
2 Correct 51 ms 10456 KB Output is correct
3 Correct 51 ms 10452 KB Output is correct
4 Correct 50 ms 10572 KB Output is correct
5 Correct 61 ms 10312 KB Output is correct
6 Correct 55 ms 10812 KB Output is correct
7 Correct 42 ms 9988 KB Output is correct
8 Correct 55 ms 9980 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 49688 KB Output is correct
2 Correct 529 ms 49732 KB Output is correct
3 Correct 538 ms 49792 KB Output is correct
4 Correct 534 ms 49828 KB Output is correct
5 Correct 534 ms 49704 KB Output is correct
6 Correct 584 ms 49724 KB Output is correct
7 Correct 524 ms 49792 KB Output is correct
8 Correct 517 ms 49784 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 59 ms 10480 KB Output is correct
12 Correct 51 ms 10456 KB Output is correct
13 Correct 51 ms 10452 KB Output is correct
14 Correct 50 ms 10572 KB Output is correct
15 Correct 61 ms 10312 KB Output is correct
16 Correct 55 ms 10812 KB Output is correct
17 Correct 42 ms 9988 KB Output is correct
18 Correct 55 ms 9980 KB Output is correct
19 Correct 583 ms 57424 KB Output is correct
20 Correct 585 ms 57364 KB Output is correct
21 Correct 584 ms 57748 KB Output is correct
22 Correct 579 ms 57160 KB Output is correct
23 Correct 586 ms 57128 KB Output is correct
24 Correct 603 ms 57552 KB Output is correct