oj.uz

Submission #646412

# Submission time Handle Problem Language Result Execution time Memory
646412 2022-09-29T18:38:06 Z Alex_tz307 Park (BOI16_park) C++17
100 / 100
 511 ms 70328 KB 
#include <bits/stdc++.h>

using namespace std;
using ld = long double;

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;
  ld r;

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

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

struct query_t {
  ld r;
  int 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;
  ld 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));
  }
}

/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

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;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:136:30: warning: narrowing conversion of '(y - r)' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  136 |     edges.push_back({i, n, y - r});
      |                            ~~^~~
park.cpp:137:38: warning: narrowing conversion of '((w - x) - r)' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  137 |     edges.push_back({i, n + 1, w - x - r});
      |                                ~~~~~~^~~
park.cpp:138:38: warning: narrowing conversion of '((h - y) - r)' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  138 |     edges.push_back({i, n + 2, h - y - r});
      |                                ~~~~~~^~~
park.cpp:139:34: warning: narrowing conversion of '(x - r)' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  139 |     edges.push_back({i, n + 3, x - r});
      |                                ~~^~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 66164 KB Output is correct
2 Correct 404 ms 66164 KB Output is correct
3 Correct 388 ms 66180 KB Output is correct
4 Correct 393 ms 66200 KB Output is correct
5 Correct 412 ms 66164 KB Output is correct
6 Correct 425 ms 66376 KB Output is correct
7 Correct 377 ms 66168 KB Output is correct
8 Correct 388 ms 66224 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 4756 KB Output is correct
2 Correct 71 ms 5760 KB Output is correct
3 Correct 61 ms 5736 KB Output is correct
4 Correct 67 ms 5828 KB Output is correct
5 Correct 74 ms 5728 KB Output is correct
6 Correct 65 ms 5828 KB Output is correct
7 Correct 61 ms 5084 KB Output is correct
8 Correct 60 ms 5040 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 66164 KB Output is correct
2 Correct 404 ms 66164 KB Output is correct
3 Correct 388 ms 66180 KB Output is correct
4 Correct 393 ms 66200 KB Output is correct
5 Correct 412 ms 66164 KB Output is correct
6 Correct 425 ms 66376 KB Output is correct
7 Correct 377 ms 66168 KB Output is correct
8 Correct 388 ms 66224 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 65 ms 4756 KB Output is correct
12 Correct 71 ms 5760 KB Output is correct
13 Correct 61 ms 5736 KB Output is correct
14 Correct 67 ms 5828 KB Output is correct
15 Correct 74 ms 5728 KB Output is correct
16 Correct 65 ms 5828 KB Output is correct
17 Correct 61 ms 5084 KB Output is correct
18 Correct 60 ms 5040 KB Output is correct
19 Correct 469 ms 70272 KB Output is correct
20 Correct 468 ms 70288 KB Output is correct
21 Correct 468 ms 70300 KB Output is correct
22 Correct 497 ms 70316 KB Output is correct
23 Correct 511 ms 70328 KB Output is correct
24 Correct 433 ms 70280 KB Output is correct