제출 #1012881

#제출 시각아이디문제언어결과실행 시간메모리
1012881imannPark (BOI16_park)C++17
0 / 100
280 ms33472 KiB
#include <iostream> #include <array> #include <algorithm> #include <cmath> #include <set> const int MAX_N = 2*1000+1; struct Tree { int x, y, r; }; struct Node { int x, y; }; struct Edge { int s, e; double l; }; std::array<Tree, MAX_N> trees; std::array<Node, 5 * MAX_N> nodes; std::vector<Edge> edges; std::array<std::array<double, 5>, 5> minAt; class Dsu { public: std::array<int, 5 * MAX_N> parents, sizes; std::array<std::set<int>, 5 * MAX_N> tags; // down : 0, right : 1, up : 2, left : 3 Dsu(int n, int w, int h) { for (int i = 0; i < 5 * n; ++i) { parents[i] = i; sizes[i] = 1; if (nodes[i].y == 0) tags[i].insert(0); if (nodes[i].x == w) tags[i].insert(1); if (nodes[i].y == h) tags[i].insert(2); if (nodes[i].x == 0) tags[i].insert(3); } } int find(int x) { if (parents[x] == x) return x; return find(parents[x]); } void unite(int x, int y, double l) { int px = find(x); int py = find(y); if (px == py) { return; } if (sizes[px] < sizes[py]) { std::swap(px, py); } parents[py] = px; sizes[px] += sizes[py]; for (int t : tags[py]) { tags[px].insert(t); } tags[py].clear(); bool zeroOk = tags[px].find(0) != tags[px].end(); bool oneOk = tags[px].find(1) != tags[px].end(); bool twoOk = tags[px].find(2) != tags[px].end(); bool threeOk = tags[px].find(3) != tags[px].end(); if (zeroOk && oneOk && minAt[0][1] == 0) { minAt[0][1] = l; minAt[1][0] = l; } if (zeroOk && twoOk && minAt[0][2] == 0) { minAt[0][2] = l; minAt[2][0] = l; } if (zeroOk && threeOk && minAt[0][3] == 0) { minAt[0][3] = l; minAt[3][0] = l; } if (oneOk && twoOk && minAt[1][2] == 0) { minAt[1][2] = l; minAt[2][1] = l; } if (oneOk && threeOk && minAt[1][3] == 0) { minAt[1][3] = l; minAt[3][1] = l; } if (twoOk && threeOk && minAt[2][3] == 0) { minAt[2][3] = l; minAt[3][2] = l; } } }; void solve(int n, int w, int h) { std::sort(edges.begin(), edges.end(), [](const Edge &l, const Edge &r) { return l.l < r.l; }); auto dsu = new Dsu(n, w, h); for (auto e : edges) { dsu->unite(e.s, e.e, e.l); } } int main() { int n, m; std::cin >> n >> m; int w, h; std::cin >> w >> h; for (int i = 0; i < n; ++i) { std::cin >> trees[i].x >> trees[i].y >> trees[i].r; } for (int i = 0; i < n; ++i) { nodes[i] = {trees[i].x, trees[i].y}; } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { double xDiff = (nodes[j].x - nodes[i].x); double yDiff = (nodes[j].y - nodes[i].y); double l = std::sqrt(xDiff * xDiff + yDiff * yDiff); edges.push_back({i, j, l - trees[i].r - trees[j].r}); } } for (int i = 0; i < n; ++i) { nodes[n + 4 * i] = {nodes[i].x, 0}; edges.push_back({i, n + 4 * i, double(nodes[i].y - trees[i].r)}); nodes[n + 4 * i + 1] = {w, nodes[i].y}; edges.push_back({i, n + 4 * i + 1, double(w - nodes[i].x - trees[i].r)}); nodes[n + 4 * i + 2] = {nodes[i].x, h}; edges.push_back({i, n + 4 * i + 2, double(h - nodes[i].y - trees[i].r)}); nodes[n + 4 * i + 3] = {0, nodes[i].y}; edges.push_back({i, n + 4 * i + 3, double(nodes[i].x - trees[i].r)}); } solve(n, w, h); for (int i = 0; i < m; ++i) { int r, e; std::cin >> r >> e; e--; std::set<int> ans; double d = 2 * r; ans.insert(e); if (d <= minAt[e][(e + 1) % 4] && d <= minAt[e][(e + 2) % 4] && d <= minAt[e][(e + 3) % 4]) { ans.insert((e + 1) % 4); } if (d <= minAt[e][(e + 3) % 4] && d <= minAt[e][(e + 2) % 4] && d <= minAt[(e + 1) % 4][(e + 2) % 4] && d <= minAt[(e + 1) % 4][(e + 3) % 4]) { ans.insert((e + 2) % 4); } if (d <= minAt[e][(e + 3) % 4] && d <= minAt[(e + 2) % 4][(e + 3) % 4] && d <= minAt[(e + 1) % 4][(e + 3) % 4]) { ans.insert((e + 3) % 4); } for (int a : ans) std::cout << a + 1; std::cout << std::endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...