Submission #513764

#	Time	Username	Problem	Language	Result	Execution time	Memory
513764		chenwz	Park (BOI16_park)	C++11	100 / 100	871 ms	53328 KiB

park

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define _all(i, a, b) for (int i = (a); i <= (int)(b); ++i)

const int VV = 5050;
int T, P, W, H, fa[VV];
LL tx[VV], ty[VV], tr[VV];  // fa[VV];
int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }
void merge(int a, int b) { a = find(a), b = find(b), fa[a] = b; }
// Trees T, T + 1, T + 2, T + 3 are the bottom, right, top and left borders.
bool overlap(LL time, LL tree1, LL tree2) {
  if (tree1 >= T) {
    if (tree2 >= T) {
      return false;
    } else {
      if (tree1 == T) return ty[tree2] - tr[tree2] - time < time;
      if (tree1 == T + 1) return tx[tree2] + tr[tree2] + time > W - time;
      if (tree1 == T + 2) return ty[tree2] + tr[tree2] + time > H - time;
      if (tree1 == T + 3) return tx[tree2] - tr[tree2] - time < time;
      throw 5;
      return false;
    }
  } else {
    if (tree2 >= T) {
      return overlap(time, tree2, tree1);
    } else {
      LL dx = tx[tree1] - tx[tree2];
      LL dy = ty[tree1] - ty[tree2];
      LL dist2 = dx * dx + dy * dy;
      LL maxdist2 = tr[tree1] + tr[tree2] + 2 * time;
      maxdist2 *= maxdist2;
      return dist2 < maxdist2;
    }
  }
}

int main() {
  _for(i, 0, VV) fa[i] = i;
  // for (int i = 0; i < VV; ++i)
  cin.sync_with_stdio(false), cin.tie(0);
  cin >> T >> P;
  cin >> W >> H;
  _for(i, 0, T) cin >> tx[i] >> ty[i] >> tr[i];
  // for (LL t = 0; t < T; ++t)

  // ((radius, corner), order)
  vector<pair<pair<LL, LL>, LL>> Q(P);
  for (LL p = 0; p < P; ++p) {
    cin >> Q[p].first.first >> Q[p].first.second;
    --Q[p].first.second;
    Q[p].second = p;
  }
  sort(Q.begin(), Q.end());

  // (time, (tree1, tree2))
  vector<pair<LL, pair<LL, LL>>> events;
  for (LL i = 0; i < T + 4; ++i) {
    for (LL j = i + 1; j < T + 4; ++j) {
      LL A = 0;
      LL B = W + H + 5;
      while (A != B) {
        LL M = (A + B) / 2;
        if (overlap(M, i, j)) {
          B = M;
        } else {
          A = M + 1;
        }
      }
      events.emplace_back(A, make_pair(i, j));
    }
  }
  sort(events.begin(), events.end());

  vector<array<bool, 4>> res(P);
  LL evi = 0;
  for (auto q : Q) {
    while (evi != (LL)events.size() && events[evi].first <= q.first.first) {
      merge(events[evi].second.first, events[evi].second.second);
      ++evi;
    }
    LL c = q.first.second;
    array<bool, 4>& r = res[q.second];
    auto conn = [c](LL a, LL b) {
      return find(T + (c + a) % 4) == find(T + (c + b) % 4);
    };
    r[c] = true;
    if (!conn(0, 1) && !conn(0, 2) && !conn(0, 3)) r[(c + 1) % 4] = true;
    if (!conn(0, 2) && !conn(0, 3) && !conn(1, 2) && !conn(1, 3))
      r[(c + 2) % 4] = true;
    if (!conn(3, 0) && !conn(3, 1) && !conn(3, 2)) r[(c + 3) % 4] = true;
  }
  for (array<bool, 4> r : res) {
    for (LL i = 0; i < 4; ++i) {
      if (r[i]) {
        cout << i + 1;
      }
    }
    cout << '\n';
  }
  return 0;
}

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