제출 #554285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554285		Soumya1	Park (BOI16_park)	C++17	100 / 100	507 ms	25468 KiB

park

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
using ll = long long;
const int mxN = 2e3 + 5;
int par[mxN];
int timer[4][4];
int find(int u) {
  return par[u] = (u == par[u] ? u : find(par[u]));
}
bool unite(int u, int v) {
  u = find(u);
  v = find(v);
  if (u == v) return false;
  par[u] = v;
  return true;
}
ll sq(int x) { return 1LL * x * x; }
int distance(int x1, int y1, int x2, int y2, int r1, int r2) {
  int d = sqrt(sq(x1 - x2) + sq(y1 - y2));
  return d - r1 - r2;
}
void testCase() {
  int n, m, w, h;
  cin >> n >> m >> w >> h;
  vector<array<int, 3>> points(n);
  vector<tuple<int, int, int>> edges;
  auto add = [&](int i, int j, int d) {
    edges.push_back({d, i, j});
  };
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 3; j++) cin >> points[i][j];
    for (int j = 0; j < i; j++) {
      add(j + 4, i + 4, distance(points[i][0], points[i][1], points[j][0], points[j][1], points[i][2], points[j][2]));
    }
    add(0, i + 4, distance(points[i][0], points[i][1], points[i][0], h, points[i][2], 0));
    add(1, i + 4, distance(points[i][0], points[i][1], points[i][0], 0, points[i][2], 0));
    add(2, i + 4, distance(points[i][0], points[i][1], 0, points[i][1], points[i][2], 0));
    add(3, i + 4, distance(points[i][0], points[i][1], w, points[i][1], points[i][2], 0));
  }
  for (int i = 0; i <= n + 4; i++) par[i] = i;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) timer[i][j] = 1e9;
  }
  sort(edges.begin(), edges.end());
  for (auto [w, u, v] : edges) {
    unite(u, v);
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        if (find(i) == find(j)) timer[i][j] = min(timer[i][j], w);
      }
    }
  }
  while (m--) {
    int r, e;
    cin >> r >> e;
    r *= 2;
    e--;
    for (int i = 0; i < 4; i++) {
      if (i == e) {
        cout << i + 1;
        continue;
      }
      int dd = 1e9;
      int a = min(i, e), b = max(i, e);
      if (a == 0 && b == 1) {
        dd = min({timer[0][1], timer[1][2], timer[1][3]});
      } else if (a == 0 && b == 2) {
        dd = min({timer[0][1], timer[2][3], timer[1][2], timer[0][3]});
      } else if (a == 0 && b == 3) {
        dd = min({timer[2][3], timer[2][0], timer[2][1]});
      } else if (a == 1 && b == 2) {
        dd = min({timer[2][3], timer[3][0], timer[3][1]});
      } else if (a == 1 && b == 3) {
        dd = min({timer[0][1], timer[2][3], timer[0][2], timer[1][3]});
      } else if (a == 2 && b == 3) {
        dd = min({timer[0][1], timer[0][2], timer[0][3]});
      }
      if (dd >= r) cout << i + 1;
    }
    cout << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42