| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 973341 |
2024-05-01T19:09:54 Z |
jakobrs |
Park (BOI16_park) |
C++17 |
|
388 ms |
67516 KB |
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <variant>
#include <vector>
template <typename... T> struct overloaded : public T... {
using T::operator()...;
};
template <typename... T> overloaded(T...) -> overloaded<T...>;
struct Time {
int64_t integral;
int64_t rooted;
template <bool EQ> auto compare(Time rhs) const -> bool {
/*
i + sqrt(r) < i1 + sqrt(r1)
sqrt(r) < id + sqrt(r1)
r < id^2 + 2 id sqrt(r1) + r1
r - id^2 - r1 < 2 id sqrt(r1)
(r - r1 - id^2)^2 < 4 id^2 r1
// i^2 - r < (i1 + sqrt(r1))(i - sqrt(r))
// = i*i1 + i sqrt(r1) - i sqrt(r) + sqrt(r r1)
*/
using i128 = __int128_t;
// using i128 = int64_t;
if (rhs.integral < integral)
return !rhs.compare<true>(*this);
auto id = rhs.integral - integral;
auto lhs_pre_square = rooted - rhs.rooted - id * id;
// std::cerr << lhs_pre_square << '\n';
if (lhs_pre_square < 0) {
return true;
}
auto lhs_eval = (i128)lhs_pre_square;
lhs_eval *= lhs_eval;
i128 rhs_eval = rhs.rooted;
rhs_eval *= 4 * id * id;
// std::cerr << "Comparing " << integral << " + sqrt(" << rooted << ") < "
// << rhs.integral << " + sqrt(" << rhs.rooted << ") <==> "
// << lhs_eval << " < " << rhs_eval << "\n";
return lhs_eval < rhs_eval || (EQ && lhs_eval == rhs_eval);
}
auto operator<(Time rhs) const -> bool { return this->compare<false>(rhs); }
};
struct UnionFind {
std::vector<int> parent;
UnionFind(int n) : parent(n, -1) {}
auto find(int idx) -> int {
if (parent[idx] < 0)
return idx;
else
return parent[idx] = find(parent[idx]);
}
auto unite(int l, int r) -> bool {
l = find(l);
r = find(r);
if (l == r)
return false;
if (-parent[l] < -parent[r])
std::swap(l, r);
parent[l] += parent[r];
parent[r] = l;
return true;
}
};
int main() {
int n, m;
std::cin >> n >> m;
int w, h;
std::cin >> w >> h;
struct Tree {
int x, y, r;
};
auto trees = std::vector<Tree>(n);
for (auto &tree : trees)
std::cin >> tree.x >> tree.y >> tree.r;
auto answers = std::vector<std::bitset<4>>(m);
struct Event {
struct Tree {
int u, v;
};
struct Query {
int c;
int id;
};
Time time;
std::variant<Tree, Query> data;
auto operator<(const Event &rhs) const -> bool {
return std::pair{time, std::holds_alternative<Query>(data)} <
std::pair{rhs.time, std::holds_alternative<Query>(rhs.data)};
}
};
auto events = std::vector<Event>{};
auto left = n + 0;
auto bottom = n + 1;
auto right = n + 2;
auto top = n + 3;
for (int i = 0; i < trees.size(); i++) {
for (int j = i + 1; j < trees.size(); j++) {
// sqrt(dx^2 + dy^2) - r1 - r2
auto dx = trees[j].x - trees[i].x;
auto dy = trees[j].y - trees[i].y;
auto r1 = trees[i].r;
auto r2 = trees[j].r;
auto dist = std::sqrt(dx * dx + dy * dy);
auto time = Time{
.integral = -r1 - r2,
.rooted = dx * dx + dy * dy,
};
// std::cerr << time.integral << " " << time.rooted << "\n";
events.push_back(Event{
.time = time,
.data = {Event::Tree{i, j}},
});
}
// edges
auto [x, y, r] = trees[i];
events.push_back(Event{
.time = Time{.integral = x - r, .rooted = 0},
.data = {Event::Tree{i, left}},
});
events.push_back(Event{
.time = Time{.integral = w - x - r, .rooted = 0},
.data = {Event::Tree{i, right}},
});
events.push_back(Event{
.time = Time{.integral = y - r, .rooted = 0},
.data = {Event::Tree{i, bottom}},
});
events.push_back(Event{
.time = Time{.integral = h - y - r, .rooted = 0},
.data = {Event::Tree{i, top}},
});
}
for (int i = 0; i < m; i++) {
int r, c;
std::cin >> r >> c;
events.push_back(Event{
.time = Time{.integral = 2 * r, .rooted = 0},
.data = {Event::Query{c - 1, i}},
});
}
std::sort(events.begin(), events.end());
auto dsu = UnionFind(n + 4);
for (auto event : events) {
// std::cerr << event.time.integral << " + sqrt " << event.time.rooted
// << " approx "
// << (double(event.time.integral) + std::sqrt(event.time.rooted))
// << "\n";
auto visitor = overloaded{
[&](Event::Tree data) {
// std::cerr << "Tree " << data.u << " " << data.v << "\n";
dsu.unite(data.u, data.v);
},
[&](Event::Query data) {
auto [c, i] = data;
// std::cerr << "Query " << c << " " << i << "\n";
std::bitset<4> can_reach;
for (int d = 0; d < 4; d++) {
can_reach[d] = true;
for (int x = 0; x < 4; x++) {
for (int y = 0; y < 4; y++) {
auto x_between = (c < x && x <= d) || (d < x && x <= c);
auto y_between = (c < y && y <= d) || (d < y && y <= c);
if (x_between && !y_between &&
dsu.find(n + x) == dsu.find(n + y)) {
can_reach[d] = false;
goto next;
}
}
}
next:;
}
answers[i] = can_reach;
}};
std::visit(visitor, event.data);
}
for (auto x : answers) {
for (int i = 0; i < 4; i++)
if (x[i])
std::cout << i + 1;
std::cout << '\n';
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:127:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (int i = 0; i < trees.size(); i++) {
| ~~^~~~~~~~~~~~~~
park.cpp:128:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for (int j = i + 1; j < trees.size(); j++) {
| ~~^~~~~~~~~~~~~~
park.cpp:135:12: warning: unused variable 'dist' [-Wunused-variable]
135 | auto dist = std::sqrt(dx * dx + dy * dy);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
388 ms |
67232 KB |
Output is correct |
| 2 |
Incorrect |
379 ms |
67516 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
6344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
388 ms |
67232 KB |
Output is correct |
| 2 |
Incorrect |
379 ms |
67516 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
