oj.uz

Submission #624419

# Submission time Handle Problem Language Result Execution time Memory
624419 2022-08-08T08:48:06 Z EthanKim8683 Park (BOI16_park) C++17
100 / 100
 331 ms 31248 KB 
#include <iostream>
#include <cstdio>
#include <tuple>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

using I = int;
using Lli = long long int;
using S = string;
using B = bool;

/*
it's all about the walls:

4    B    3
  |`````|
A |     | C
  |_____|
1    D    2

A <-> B separates 4 from 3, 2 and 1
A <-> C separates 4 and 3 from 2 and 1
C <-> D separates 2 from 4, 3 and 1
etc.

We can union nodes by size, increasing,
to block fatter visitors from passing
*/

const I N = 2000;
const I M = 1e5;

tuple<I, I, I> tres[N];
pair<I, I> viss[M];
vector<tuple<I, I, I>> edgs;
vector<tuple<I, I, I>> stks;
I pars[N + 4];
B cuts[4][4];
S ress[M];

I fnd(I x) {
  if (pars[x] < 0)
    return x;
  return pars[x] = fnd(pars[x]);
}

void uni(I a, I b) {
  if ((a = fnd(a)) == (b = fnd(b)))
    return;
  if (pars[a] > pars[b])
    swap(a, b);
  pars[a] += pars[b];
  pars[b] = a;
}

B con(I a, I b) {
  return fnd(a) == fnd(b);
}

I dis(I x1, I y1, I x2, I y2) {
  const Lli x = x1 - x2;
  const Lli y = y1 - y2;
  return (I) sqrt(x * x + y * y);
}

I main(void) {
  cin.tie(0)->sync_with_stdio(0);
  I n, m;
  cin >> n >> m;
  I w, h;
  cin >> w >> h;
  for (I i = 0; i < n; i++)
    cin >> get<0>(tres[i]) >> get<1>(tres[i]) >> get<2>(tres[i]);
  for (I i = 0; i < m; i++)
    cin >> get<0>(viss[i]) >> get<1>(viss[i]);
  for (I i = 0; i < m; i++)
    stks.push_back({viss[i].first * 2, viss[i].second - 1, i});
  fill_n(pars, n + 4, -1);
  edgs.push_back({w, n + 0, n + 2});
  edgs.push_back({h, n + 1, n + 3});
  for (I i = 0; i < n; i++) {
    const auto [x, y, r] = tres[i];
    edgs.push_back({x - r, i, n + 0});
    edgs.push_back({y - r, i, n + 1});
    edgs.push_back({w - x - r, i, n + 2});
    edgs.push_back({h - y - r, i, n + 3});
  }
  for (I i = 0; i < n; i++) {
    for (I j = i + 1; j < n; j++) {
      const auto [x1, y1, r1] = tres[i];
      const auto [x2, y2, r2] = tres[j];
      edgs.push_back({dis(x1, y1, x2, y2) - r1 - r2, i, j});
    }
  }
  sort(edgs.begin(), edgs.end());
  sort(stks.begin(), stks.end(), greater<tuple<I, I, I>>());
  for (const auto [len, i, j] : edgs) {
    while (!stks.empty() && get<0>(stks.back()) <= len) {
      const auto [r, e, i] = stks.back();
      stks.pop_back();
      for (I j = 0; j < 4; j++)
        if (!cuts[min(e, j)][max(e, j)])
          ress[i] += to_string(j + 1);
    }
    uni(i, j);
    if (con(n + 0, n + 1))
      cuts[0][1] = cuts[0][2] = cuts[0][3] = true;
    if (con(n + 0, n + 2))
      cuts[0][2] = cuts[0][3] = cuts[1][2] = cuts[1][3] = true;
    if (con(n + 0, n + 3))
      cuts[0][3] = cuts[1][3] = cuts[2][3] = true;
    if (con(n + 1, n + 2))
      cuts[0][1] = cuts[1][2] = cuts[1][3] = true;
    if (con(n + 1, n + 3))
      cuts[0][1] = cuts[0][2] = cuts[1][3] = cuts[2][3] = true;
    if (con(n + 2, n + 3))
      cuts[0][2] = cuts[1][2] = cuts[2][3] = true;
  }
  for (I i = 0; i < m; i++)
    printf("%s\n", ress[i].c_str());
  return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 28348 KB Output is correct
2 Correct 283 ms 28292 KB Output is correct
3 Correct 280 ms 28288 KB Output is correct
4 Correct 284 ms 28280 KB Output is correct
5 Correct 297 ms 28208 KB Output is correct
6 Correct 283 ms 28212 KB Output is correct
7 Correct 266 ms 28212 KB Output is correct
8 Correct 242 ms 28272 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7456 KB Output is correct
2 Correct 53 ms 7364 KB Output is correct
3 Correct 50 ms 7380 KB Output is correct
4 Correct 43 ms 7360 KB Output is correct
5 Correct 41 ms 7340 KB Output is correct
6 Correct 45 ms 7488 KB Output is correct
7 Correct 44 ms 6980 KB Output is correct
8 Correct 43 ms 6988 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 28348 KB Output is correct
2 Correct 283 ms 28292 KB Output is correct
3 Correct 280 ms 28288 KB Output is correct
4 Correct 284 ms 28280 KB Output is correct
5 Correct 297 ms 28208 KB Output is correct
6 Correct 283 ms 28212 KB Output is correct
7 Correct 266 ms 28212 KB Output is correct
8 Correct 242 ms 28272 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 42 ms 7456 KB Output is correct
12 Correct 53 ms 7364 KB Output is correct
13 Correct 50 ms 7380 KB Output is correct
14 Correct 43 ms 7360 KB Output is correct
15 Correct 41 ms 7340 KB Output is correct
16 Correct 45 ms 7488 KB Output is correct
17 Correct 44 ms 6980 KB Output is correct
18 Correct 43 ms 6988 KB Output is correct
19 Correct 330 ms 31216 KB Output is correct
20 Correct 329 ms 31248 KB Output is correct
21 Correct 323 ms 31240 KB Output is correct
22 Correct 327 ms 31156 KB Output is correct
23 Correct 331 ms 31232 KB Output is correct
24 Correct 317 ms 31160 KB Output is correct