oj.uz

Submission #513931

# Submission time Handle Problem Language Result Execution time Memory
513931 2022-01-18T00:30:07 Z chenwz Park (BOI16_park) C++11
100 / 100
 1042 ms 52040 KB 
// 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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 49764 KB Output is correct
2 Correct 896 ms 49732 KB Output is correct
3 Correct 887 ms 49768 KB Output is correct
4 Correct 852 ms 49812 KB Output is correct
5 Correct 855 ms 49848 KB Output is correct
6 Correct 841 ms 49736 KB Output is correct
7 Correct 826 ms 49788 KB Output is correct
8 Correct 811 ms 49728 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 3828 KB Output is correct
2 Correct 154 ms 3812 KB Output is correct
3 Correct 193 ms 3792 KB Output is correct
4 Correct 161 ms 3912 KB Output is correct
5 Correct 162 ms 3888 KB Output is correct
6 Correct 169 ms 3948 KB Output is correct
7 Correct 146 ms 3276 KB Output is correct
8 Correct 163 ms 3312 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 49764 KB Output is correct
2 Correct 896 ms 49732 KB Output is correct
3 Correct 887 ms 49768 KB Output is correct
4 Correct 852 ms 49812 KB Output is correct
5 Correct 855 ms 49848 KB Output is correct
6 Correct 841 ms 49736 KB Output is correct
7 Correct 826 ms 49788 KB Output is correct
8 Correct 811 ms 49728 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 177 ms 3828 KB Output is correct
12 Correct 154 ms 3812 KB Output is correct
13 Correct 193 ms 3792 KB Output is correct
14 Correct 161 ms 3912 KB Output is correct
15 Correct 162 ms 3888 KB Output is correct
16 Correct 169 ms 3948 KB Output is correct
17 Correct 146 ms 3276 KB Output is correct
18 Correct 163 ms 3312 KB Output is correct
19 Correct 998 ms 51872 KB Output is correct
20 Correct 1002 ms 51872 KB Output is correct
21 Correct 1042 ms 51964 KB Output is correct
22 Correct 977 ms 51968 KB Output is correct
23 Correct 991 ms 52040 KB Output is correct
24 Correct 973 ms 51960 KB Output is correct