oj.uz

Submission #646413

# Submission time Handle Problem Language Result Execution time Memory
646413 2022-09-29T18:39:41 Z Alex_tz307 Park (BOI16_park) C++17
100 / 100
 260 ms 26292 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 2e3;
const int kM = 1e5;

int Edist(int x1, int y1, int x2, int y2) {
  return sqrtl((int64_t)(x1 - x2) * (x1 - x2) + (int64_t)(y1 - y2) * (y1 - y2));
}

struct circle_t {
  int x, y, r;

  void read() {
    cin >> x >> y >> r;
  }

  int dist(const circle_t &other) {
    return Edist(x, y, other.x, other.y) - r - other.r;
  }
} t[kN];

struct query_t {
  int r, e, index;

  void read() {
    cin >> r >> e;
    r *= 2;
    e -= 1;
  }

  bool operator < (const query_t &rhs) const {
    return r < rhs.r;
  }
} q[kM];

struct edge {
  int u, v, w;

  bool operator < (const edge &rhs) const {
    return w < rhs.w;
  }
};

struct DSU {
  vector<int> p, sz;

  void init(int n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    sz.assign(n, 1);
  }

  int root(int x) {
    if (x == p[x]) {
      return x;
    }
    return p[x] = root(p[x]);
  }

  bool connected(int x, int y) {
    return root(x) == root(y);
  }

  bool unite(int u, int v) {
    int x = root(u), y = root(v);
    if (x == y) {
      return false;
    }
    if (sz[y] < sz[x]) {
      swap(x, y);
    }
    p[x] = y;
    sz[y] += sz[x];
    return true;
  }
} dsu;

int n;
short sol[kM];

void solveQuery(int p) {
  int e = q[p].e, index = q[p].index;
  sol[index] |= (1 << e);
  if (!dsu.connected(n + e, n + (e + 2) % 4) && !dsu.connected(n + e, n + (e + 3) % 4) && !dsu.connected(n + e, n + (e + 1) % 4)) {
    sol[index] |= (1 << ((e + 1) % 4));
  }
  if (!dsu.connected(n + e, n + (e + 3) % 4) && !dsu.connected(n + (e + 1) % 4, n + (e + 2) % 4) && !dsu.connected(n + e, n + (e + 2) % 4) && !dsu.connected(n + (e + 1) % 4, n + (e + 3) % 4)) {
    sol[index] |= (1 << ((e + 2) % 4));
  }
  if (!dsu.connected(n + e, n + (e + 3) % 4) && !dsu.connected(n + (e + 2) % 4, n + (e + 3) % 4) && !dsu.connected(n + (e + 1) % 4, n + (e + 3) % 4)) {
    sol[index] |= (1 << ((e + 3) % 4));
  }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int m, w, h;
  cin >> n >> m >> w >> h;

  for (int i = 0; i < n; ++i) {
    t[i].read();
  }

  for (int i = 0; i < m; ++i) {
    q[i].read();
    q[i].index = i;
  }

  vector<edge> edges;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      edges.push_back({i, j, t[i].dist(t[j])});
    }
    int x = t[i].x, y = t[i].y, r = t[i].r;
    edges.push_back({i, n, y - r});
    edges.push_back({i, n + 1, w - x - r});
    edges.push_back({i, n + 2, h - y - r});
    edges.push_back({i, n + 3, x - r});
  }

  sort(edges.begin(), edges.end());
  sort(q, q + m);

  dsu.init(n + 4);
  int ptr = 0;
  for (auto e : edges) {
    while (ptr < m && q[ptr].r <= e.w) {
      solveQuery(ptr);
      ptr += 1;
    }
    dsu.unite(e.u, e.v);
  }
  while (ptr < m) {
    solveQuery(ptr);
    ptr += 1;
  }

  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < 4; ++j) {
      if (sol[i] & (1 << j)) {
        cout << j + 1;
      }
    }
    cout << '\n';
  }

  return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 25012 KB Output is correct
2 Correct 222 ms 25092 KB Output is correct
3 Correct 221 ms 25004 KB Output is correct
4 Correct 223 ms 25008 KB Output is correct
5 Correct 225 ms 25148 KB Output is correct
6 Correct 217 ms 25028 KB Output is correct
7 Correct 197 ms 25148 KB Output is correct
8 Correct 205 ms 25024 KB Output is correct
9 Correct 0 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 42 ms 2384 KB Output is correct
2 Correct 40 ms 2396 KB Output is correct
3 Correct 40 ms 2400 KB Output is correct
4 Correct 39 ms 2392 KB Output is correct
5 Correct 40 ms 2284 KB Output is correct
6 Correct 44 ms 2384 KB Output is correct
7 Correct 35 ms 1940 KB Output is correct
8 Correct 34 ms 1988 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 25012 KB Output is correct
2 Correct 222 ms 25092 KB Output is correct
3 Correct 221 ms 25004 KB Output is correct
4 Correct 223 ms 25008 KB Output is correct
5 Correct 225 ms 25148 KB Output is correct
6 Correct 217 ms 25028 KB Output is correct
7 Correct 197 ms 25148 KB Output is correct
8 Correct 205 ms 25024 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 42 ms 2384 KB Output is correct
12 Correct 40 ms 2396 KB Output is correct
13 Correct 40 ms 2400 KB Output is correct
14 Correct 39 ms 2392 KB Output is correct
15 Correct 40 ms 2284 KB Output is correct
16 Correct 44 ms 2384 KB Output is correct
17 Correct 35 ms 1940 KB Output is correct
18 Correct 34 ms 1988 KB Output is correct
19 Correct 258 ms 26292 KB Output is correct
20 Correct 257 ms 26284 KB Output is correct
21 Correct 260 ms 26256 KB Output is correct
22 Correct 251 ms 26200 KB Output is correct
23 Correct 253 ms 26168 KB Output is correct
24 Correct 243 ms 26292 KB Output is correct