oj.uz

Submission #164726

# Submission time Handle Problem Language Result Execution time Memory
164726 2019-11-22T20:10:44 Z xiaowuc1 Park (BOI16_park) C++17
100 / 100
 476 ms 38808 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 36544 KB Output is correct
2 Correct 381 ms 36800 KB Output is correct
3 Correct 379 ms 36544 KB Output is correct
4 Correct 386 ms 36544 KB Output is correct
5 Correct 380 ms 36748 KB Output is correct
6 Correct 384 ms 36544 KB Output is correct
7 Correct 350 ms 36548 KB Output is correct
8 Correct 327 ms 36540 KB Output is correct
9 Correct 5 ms 3448 KB Output is correct
10 Correct 5 ms 3448 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 6608 KB Output is correct
2 Correct 84 ms 6536 KB Output is correct
3 Correct 81 ms 6516 KB Output is correct
4 Correct 84 ms 6516 KB Output is correct
5 Correct 85 ms 6644 KB Output is correct
6 Correct 89 ms 6528 KB Output is correct
7 Correct 71 ms 6136 KB Output is correct
8 Correct 75 ms 6136 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 36544 KB Output is correct
2 Correct 381 ms 36800 KB Output is correct
3 Correct 379 ms 36544 KB Output is correct
4 Correct 386 ms 36544 KB Output is correct
5 Correct 380 ms 36748 KB Output is correct
6 Correct 384 ms 36544 KB Output is correct
7 Correct 350 ms 36548 KB Output is correct
8 Correct 327 ms 36540 KB Output is correct
9 Correct 5 ms 3448 KB Output is correct
10 Correct 5 ms 3448 KB Output is correct
11 Correct 92 ms 6608 KB Output is correct
12 Correct 84 ms 6536 KB Output is correct
13 Correct 81 ms 6516 KB Output is correct
14 Correct 84 ms 6516 KB Output is correct
15 Correct 85 ms 6644 KB Output is correct
16 Correct 89 ms 6528 KB Output is correct
17 Correct 71 ms 6136 KB Output is correct
18 Correct 75 ms 6136 KB Output is correct
19 Correct 476 ms 38616 KB Output is correct
20 Correct 463 ms 38740 KB Output is correct
21 Correct 466 ms 38808 KB Output is correct
22 Correct 441 ms 38720 KB Output is correct
23 Correct 453 ms 38720 KB Output is correct
24 Correct 416 ms 38720 KB Output is correct