Submission #1092930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092930		duckindog	Park (BOI16_park)	C++17	100 / 100	245 ms	32136 KiB

park

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2000 + 10,
          M = 100'000 + 10;
int n, m;
int w, h;
 
struct Tree { 
  int x, y, r;
  int dist(const auto& rhs) { 
    return sqrt(1ll * (x - rhs.x) * (x - rhs.x) + 1ll * (y - rhs.y) * (y - rhs.y)) - r - rhs.r; 
  } 
  friend istream& operator >> (istream& is, auto& rhs) { 
    return is >> rhs.x >> rhs.y >> rhs.r;
  }
} tree[N];
struct Query { 
  int r, e, idx;
  friend istream& operator >> (istream& is, Query& rhs) { 
    return is >> rhs.r >> rhs.e;
  }
} query[M];
 
int id[N];
int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
void add(int u, int v) { 
  u = root(u); v = root(v);
  if (u == v) return;
  if (id[u] > id[v]) swap(u, v);
  id[u] += id[v];
  id[v] = u;
}
 
int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n >> m;
  cin >> w >> h;
 
  for (int i = 1; i <= n; ++i) cin >> tree[i];
  for (int i = 1; i <= m; ++i) cin >> query[i], query[i].idx = i;
  
  memset(id, -1, sizeof id);
  vector<tuple<int, int, int>> vt;
  for (int i = 1; i <= n; ++i) { 
    vt.emplace_back(i, n + 1, (h - tree[i].y - tree[i].r) / 2 + 1);
    vt.emplace_back(i, n + 2, (w - tree[i].x - tree[i].r) / 2 + 1);
    vt.emplace_back(i, n + 3, (tree[i].y - tree[i].r) / 2 + 1);
    vt.emplace_back(i, n + 4, (tree[i].x - tree[i].r) / 2 + 1);
 
    for (int j = 1; j < i; ++j)
      vt.emplace_back(i, j, tree[i].dist(tree[j]) / 2 + 1);
  }
  
  sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { 
    return get<2>(a) < get<2>(b);
  });
 
  sort(query + 1, query + m + 1, [&](const auto& a, const auto& b) { 
    return a.r < b.r;
  });
 
  vector<vector<int>> answer(m + 1);
  auto cal = [&](int it) { 
    const auto& [r, e, idx] = query[it];
    
    auto& ret = answer[idx];
    ret.push_back(e);
    if (e == 1 && root(n + 3) != root(n + 4)) { 
      if (root(n + 1) != root(n + 3) && root(n + 2) != root(n + 3)) ret.push_back(2);
      if (root(n + 1) != root(n + 2) && root(n + 1) != root(n + 3) && root(n + 2) != root(n + 4))
        ret.push_back(3);
      if (root(n + 1) != root(n + 4) && root(n + 2) != root(n + 4)) ret.push_back(4);
    }
 
    if (e == 2 && root(n + 2) != root(n + 3)) { 
      if (root(n + 1) != root(n + 3) && root(n + 3) != root(n + 4)) ret.push_back(1);
      if (root(n + 2) != root(n + 4) && root(n + 2) != root(n + 1)) ret.push_back(3);
      if (root(n + 1) != root(n + 3) && root(n + 2) != root(n + 4) && root(n + 1) != root(n + 4)) 
        ret.push_back(4);
    }
 
    if (e == 3 && root(n + 1) != root(n + 2)) { 
      if (root(n + 1) != root(n + 3) && root(n + 2) != root(n + 4) && root(n + 3) != root(n + 4))
        ret.push_back(1);
      if (root(n + 2) != root(n + 4) && root(n + 2) != root(n + 3)) ret.push_back(2);
      if (root(n + 1) != root(n + 3) && root(n + 1) != root(n + 4)) ret.push_back(4);
    }
 
    if (e == 4 && root(n + 4) != root(n + 1)) { 
      if (root(n + 2) != root(n + 4) && root(n + 3) != root(n + 4)) ret.push_back(1);
      if (root(n + 2) != root(n + 4) && root(n + 1) != root(n + 3) && root(n + 2) != root(n + 3))
        ret.push_back(2);
      if (root(n + 1) != root(n + 3) && root(n + 1) != root(n + 2)) ret.push_back(3);
    }
  };
  
  int it = 1;
  for (const auto& [u, v, w] : vt) { 
    while (it <= m && query[it].r < w) cal(it++);
    add(u, v);
  }
  while (it <= m) cal(it++);
 
  for (int i = 1; i <= m; ++i) { 
    auto& ret = answer[i];
    sort(ret.begin(), ret.end());
    
    for (const auto& x : ret) cout << x;
    cout << "\n";
  }
}

Compilation message (stderr)

park.cpp:12:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 |   int dist(const auto& rhs) {
      |                  ^~~~
park.cpp:15:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   15 |   friend istream& operator >> (istream& is, auto& rhs) {
      |                                             ^~~~

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