제출 #164726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164726		xiaowuc1	Park (BOI16_park)	C++17	100 / 100	476 ms	38808 KiB

park

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef vector<int> vi;
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pii, int> query; // <radius, entrance>, idx
typedef long double ld;
typedef pair<double, pii> event; // distance, <a, b>

int par[2005];
const int NORTH = 2000;
const int EAST = 2001;
const int SOUTH = 2002;
const int WEST = 2003;

int find(int x) {
  return par[x] == x ? x : (par[x] = find(par[x]));
}
void merge(int x, int y) {
  par[find(x)] = find(y);
}

query queries[100005];
string ret[100005];
int n, q;
int maxX, maxY;
int x[2005];
int y[2005];
int r[2005];

bool canReach(int a, int b) {
  // BL BR TR TL
  assert(min(a, b) >= 1 && max(a, b) <= 4);
  if(a == b) return true;
  if(a > b) swap(a, b);
  if(a == 1 && b == 2) {
    return find(SOUTH) != find(NORTH) && find(SOUTH) != find(WEST) && find(SOUTH) != find(EAST);
  }
  if(a == 1 && b == 3) {
    if(find(WEST) == find(SOUTH)) return false;
    if(find(WEST) == find(EAST)) return false;
    if(find(SOUTH) == find(NORTH)) return false;
    if(find(EAST) == find(NORTH)) return false;
    return true;
  }
  if(a == 1 && b == 4) {
    if(find(WEST) == find(NORTH)) return false;
    if(find(WEST) == find(SOUTH)) return false;
    if(find(WEST) == find(EAST)) return false;
    return true;
  }
  if(a == 2 && b == 3) {
    if(find(EAST) == find(WEST)) return false;
    if(find(EAST) == find(NORTH)) return false;
    if(find(EAST) == find(SOUTH)) return false;
    return true;
  }
  if(a == 2 && b == 4) {
    if(find(EAST) == find(SOUTH)) return false;
    if(find(NORTH) == find(SOUTH)) return false;
    if(find(WEST) == find(EAST)) return false;
    if(find(NORTH) == find(WEST)) return false;
    return true;
  }
  if(a == 3 && b == 4) {
    if(find(NORTH) == find(WEST)) return false;
    if(find(NORTH) == find(EAST)) return false;
    if(find(NORTH) == find(SOUTH)) return false;
    return true;
  }
  assert(false);
}

void fillRet(int idx) {
  // query index
  for(int a = 1; a <= 4; a++) {
    if(canReach(queries[idx].first.second, a)) {
      ret[queries[idx].second] += to_string(a);
    }
  }
}

void solve() {
  cin >> n >> q >> maxX >> maxY;
  for(int i = 0; i <= WEST; i++) par[i] = i;
  for(int i = 0; i < n; i++) cin >> x[i] >> y[i] >> r[i];
  for(int i = 0; i < q; i++) {
    cin >> queries[i].first.first >> queries[i].first.second;
    queries[i].first.first *= 2;
    queries[i].second = i;
  }
  sort(queries, queries+q);
  vector<event> events;
  for(int i = 0; i < n; i++) {
    events.push_back(event(maxY - y[i] - r[i], {NORTH, i}));
    events.push_back(event(y[i] - r[i], {SOUTH, i}));
    events.push_back(event(x[i] - r[i], {WEST, i}));
    events.push_back(event(maxX - x[i] - r[i], {EAST, i}));
    for(int j = 0; j < i; j++) {
      events.push_back(event(hypot(y[i] - y[j], x[i] - x[j]) - r[i] - r[j], {i, j}));
    }
  }
  sort(events.begin(), events.end());
  int idx = 0;
  for(int i = 0; i < q; i++) {
    while(idx < sz(events) && events[idx].first < queries[i].first.first) {
      merge(events[idx].second.first, events[idx].second.second);
      idx++;
    }
    fillRet(i);
  }
  for(int i = 0; i < q; i++) cout << ret[i] << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}

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