oj.uz

Submission #1092930

# Submission time Handle Problem Language Result Execution time Memory
1092930 2024-09-25T12:31:23 Z duckindog Park (BOI16_park) C++17
100 / 100
 245 ms 32136 KB 
#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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 25280 KB Output is correct
2 Correct 192 ms 25268 KB Output is correct
3 Correct 194 ms 25180 KB Output is correct
4 Correct 200 ms 25280 KB Output is correct
5 Correct 212 ms 25280 KB Output is correct
6 Correct 203 ms 25284 KB Output is correct
7 Correct 174 ms 25280 KB Output is correct
8 Correct 182 ms 25284 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 8560 KB Output is correct
2 Correct 41 ms 8568 KB Output is correct
3 Correct 46 ms 8588 KB Output is correct
4 Correct 49 ms 8780 KB Output is correct
5 Correct 42 ms 8528 KB Output is correct
6 Correct 43 ms 8784 KB Output is correct
7 Correct 36 ms 8532 KB Output is correct
8 Correct 37 ms 8540 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 25280 KB Output is correct
2 Correct 192 ms 25268 KB Output is correct
3 Correct 194 ms 25180 KB Output is correct
4 Correct 200 ms 25280 KB Output is correct
5 Correct 212 ms 25280 KB Output is correct
6 Correct 203 ms 25284 KB Output is correct
7 Correct 174 ms 25280 KB Output is correct
8 Correct 182 ms 25284 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 45 ms 8560 KB Output is correct
12 Correct 41 ms 8568 KB Output is correct
13 Correct 46 ms 8588 KB Output is correct
14 Correct 49 ms 8780 KB Output is correct
15 Correct 42 ms 8528 KB Output is correct
16 Correct 43 ms 8784 KB Output is correct
17 Correct 36 ms 8532 KB Output is correct
18 Correct 37 ms 8540 KB Output is correct
19 Correct 245 ms 32064 KB Output is correct
20 Correct 229 ms 31840 KB Output is correct
21 Correct 231 ms 32136 KB Output is correct
22 Correct 235 ms 31880 KB Output is correct
23 Correct 239 ms 31876 KB Output is correct
24 Correct 228 ms 32132 KB Output is correct