oj.uz

Submission #513799

# Submission time Handle Problem Language Result Execution time Memory
513799 2022-01-17T16:02:43 Z chenwz Park (BOI16_park) C++11
100 / 100
 891 ms 56404 KB 
#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 &t1 = Ts[i], t2 = Ts[j];
  if (i >= T) {
    if (j >= T) return false;
    if (i == T) return t2.y - t2.r - time < time;
    if (i == T + 1) return t2.x + t2.r + time > W - time;
    if (i == T + 2) return t2.y + t2.r + time > H - time;
    if (i == T + 3) return t2.x - t2.r - time < time;
    throw 5;
    return false;
  } else {
    if (j >= T) return overlap(time, j, i);
    LL dx = t1.x - t2.x, dy = t1.y - t2.y;
    LL maxd2 = t1.r + t2.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;
  _for(i, 0, T) cin >> Ts[i].x >> Ts[i].y >> Ts[i].r;

  using VI = vector<int>;
  vector<VI> Q(P);
  _for(i, 0, P) {
    int r, e;
    cin >> r >> e, Q[i] = {r, e - 1, i};
  }
  sort(Q.begin(), Q.end());
  vector<pair<LL, pair<LL, LL>>> 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.emplace_back(A, make_pair(i, j));
  }
  sort(es.begin(), es.end());
  vector<array<bool, 4>> res(P);
  int ei = 0;
  for (auto q : Q) {
    while (ei < (int)es.size() && es[ei].first <= q[0]) {
      unite(es[ei].second.first, es[ei].second.second);
      ++ei;
    }
    int c = q[1];
    array<bool, 4>& r = res[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 : res) {
    _for(i, 0, 4) if (r[i]) cout << i + 1;
    cout << '\n';
  }
  return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 49840 KB Output is correct
2 Correct 818 ms 49756 KB Output is correct
3 Correct 809 ms 49760 KB Output is correct
4 Correct 810 ms 49800 KB Output is correct
5 Correct 823 ms 49920 KB Output is correct
6 Correct 827 ms 49784 KB Output is correct
7 Correct 753 ms 49732 KB Output is correct
8 Correct 746 ms 49676 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 7200 KB Output is correct
2 Correct 71 ms 8192 KB Output is correct
3 Correct 77 ms 8084 KB Output is correct
4 Correct 71 ms 8164 KB Output is correct
5 Correct 71 ms 8212 KB Output is correct
6 Correct 75 ms 8220 KB Output is correct
7 Correct 61 ms 7640 KB Output is correct
8 Correct 57 ms 7608 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 49840 KB Output is correct
2 Correct 818 ms 49756 KB Output is correct
3 Correct 809 ms 49760 KB Output is correct
4 Correct 810 ms 49800 KB Output is correct
5 Correct 823 ms 49920 KB Output is correct
6 Correct 827 ms 49784 KB Output is correct
7 Correct 753 ms 49732 KB Output is correct
8 Correct 746 ms 49676 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 66 ms 7200 KB Output is correct
12 Correct 71 ms 8192 KB Output is correct
13 Correct 77 ms 8084 KB Output is correct
14 Correct 71 ms 8164 KB Output is correct
15 Correct 71 ms 8212 KB Output is correct
16 Correct 75 ms 8220 KB Output is correct
17 Correct 61 ms 7640 KB Output is correct
18 Correct 57 ms 7608 KB Output is correct
19 Correct 884 ms 56264 KB Output is correct
20 Correct 891 ms 56316 KB Output is correct
21 Correct 878 ms 56300 KB Output is correct
22 Correct 887 ms 56360 KB Output is correct
23 Correct 868 ms 56404 KB Output is correct
24 Correct 867 ms 56160 KB Output is correct