Submission #513931

#	Time	Username	Problem	Language	Result	Execution time	Memory
513931		chenwz	Park (BOI16_park)	C++11	100 / 100	1042 ms	52040 KiB

park

// Baltic OI 2016 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];
struct Circle {
  int x, y, r;
};
Circle Ts[VV];
int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }
void unite(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(int time, int i, int j) {
  const Circle &ti = Ts[i], tj = Ts[j];
  if (i >= T) {
    if (j >= T) return false;
    if (i == T) return tj.y - tj.r - time < time;
    if (i == T + 1) return tj.x + tj.r + time > W - time;
    if (i == T + 2) return tj.y + tj.r + time > H - time;
    if (i == T + 3) return tj.x - tj.r - time < time;
    throw 5;
    return false;
  } else {
    if (j >= T) return overlap(time, j, i);
    LL dx = ti.x - tj.x, dy = ti.y - tj.y;
    LL maxd2 = ti.r + tj.r + 2 * time;
    return dx * dx + dy * dy < maxd2 * maxd2;
  }
}

int main() {
  _for(i, 0, VV) fa[i] = i;
  cin.sync_with_stdio(false), cin.tie(0);
  cin >> T >> P;  // 树,人
  cin >> W >> H;  // W*H
  _for(i, 0, T) cin >> Ts[i].x >> Ts[i].y >> Ts[i].r;
  vector<array<int, 3>> Q(P);
  _for(i, 0, P) {
    int r, e;
    cin >> r >> e, Q[i] = {r, e - 1, i};
  }
  sort(Q.begin(), Q.end());
  vector<array<LL, 3>> es;  // (time, (tree1, tree2))
  _for(i, 0, T + 4) _for(j, i + 1, T + 4) {
    LL A = 0, B = W + H + 5;
    while (A != B) {
      LL M = (A + B) / 2;
      overlap(M, i, j) ? (B = M) : (A = M + 1);
    }
    es.push_back({A, i, j});
  }
  sort(es.begin(), es.end());
  vector<array<bool, 4>> ans(P);
  size_t ei = 0;
  for (auto q : Q) {
    for (; ei < es.size() && es[ei][0] <= q[0]; ei++)
      unite(es[ei][1], es[ei][2]);
    int c = q[1];  // 四角之一
    auto& r = ans[q[2]];
    auto conn = [c](int a, int 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 (const auto& r : ans) {
    _for(i, 0, 4) if (r[i]) cout << i + 1;
    cout << endl;
  }
  return 0;
}

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