oj.uz

Submission #1092912

# Submission time Handle Problem Language Result Execution time Memory
1092912 2024-09-25T11:11:55 Z duckindog Park (BOI16_park) C++17
27 / 100
 456 ms 99204 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

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 <= n; ++j)
      if (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)) 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:14:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   14 |   int dist(const auto& rhs) { return sqrt(1ll * (x - rhs.x) * (x - rhs.x) + 1ll * (y - rhs.y) * (y - rhs.y)) - r - rhs.r; }
      |                  ^~~~
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 435 ms 99204 KB Output is correct
2 Correct 433 ms 99160 KB Output is correct
3 Correct 433 ms 99156 KB Output is correct
4 Correct 442 ms 99144 KB Output is correct
5 Correct 450 ms 99152 KB Output is correct
6 Correct 456 ms 99204 KB Output is correct
7 Correct 418 ms 99152 KB Output is correct
8 Correct 421 ms 99148 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 11780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 99204 KB Output is correct
2 Correct 433 ms 99160 KB Output is correct
3 Correct 433 ms 99156 KB Output is correct
4 Correct 442 ms 99144 KB Output is correct
5 Correct 450 ms 99152 KB Output is correct
6 Correct 456 ms 99204 KB Output is correct
7 Correct 418 ms 99152 KB Output is correct
8 Correct 421 ms 99148 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 47 ms 11780 KB Output isn't correct
12 Halted 0 ms 0 KB -