oj.uz

Submission #1012884

# Submission time Handle Problem Language Result Execution time Memory
1012884 2024-07-02T19:29:46 Z imann Park (BOI16_park) C++17
100 / 100
 490 ms 34312 KB 
#include <iostream>
#include <array>
#include <algorithm>
#include <cmath>
#include <set>

const int MAX_N = 2*1000+1;
const double EPS = 1e-3;

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 + EPS;
            minAt[1][0] = l + EPS;
        }
        if (zeroOk && twoOk && minAt[0][2] == 0) {
            minAt[0][2] = l + EPS;
            minAt[2][0] = l + EPS;
        }
        if (zeroOk && threeOk && minAt[0][3] == 0) {
            minAt[0][3] = l + EPS;
            minAt[3][0] = l + EPS;
        }
        if (oneOk && twoOk && minAt[1][2] == 0) {
            minAt[1][2] = l + EPS;
            minAt[2][1] = l + EPS;
        }
        if (oneOk && threeOk && minAt[1][3] == 0) {
            minAt[1][3] = l + EPS;
            minAt[3][1] = l + EPS;
        }
        if (twoOk && threeOk && minAt[2][3] == 0) {
            minAt[2][3] = l + EPS;
            minAt[3][2] = l + EPS;
        }
    }
};

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;
    }
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 33460 KB Output is correct
2 Correct 282 ms 33472 KB Output is correct
3 Correct 281 ms 33472 KB Output is correct
4 Correct 281 ms 33480 KB Output is correct
5 Correct 281 ms 33460 KB Output is correct
6 Correct 277 ms 33468 KB Output is correct
7 Correct 225 ms 33460 KB Output is correct
8 Correct 219 ms 33460 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 2764 KB Output is correct
2 Correct 182 ms 2580 KB Output is correct
3 Correct 210 ms 2564 KB Output is correct
4 Correct 134 ms 2652 KB Output is correct
5 Correct 142 ms 2760 KB Output is correct
6 Correct 139 ms 2760 KB Output is correct
7 Correct 139 ms 2260 KB Output is correct
8 Correct 163 ms 2380 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 33460 KB Output is correct
2 Correct 282 ms 33472 KB Output is correct
3 Correct 281 ms 33472 KB Output is correct
4 Correct 281 ms 33480 KB Output is correct
5 Correct 281 ms 33460 KB Output is correct
6 Correct 277 ms 33468 KB Output is correct
7 Correct 225 ms 33460 KB Output is correct
8 Correct 219 ms 33460 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct
11 Correct 155 ms 2764 KB Output is correct
12 Correct 182 ms 2580 KB Output is correct
13 Correct 210 ms 2564 KB Output is correct
14 Correct 134 ms 2652 KB Output is correct
15 Correct 142 ms 2760 KB Output is correct
16 Correct 139 ms 2760 KB Output is correct
17 Correct 139 ms 2260 KB Output is correct
18 Correct 163 ms 2380 KB Output is correct
19 Correct 490 ms 34160 KB Output is correct
20 Correct 406 ms 34052 KB Output is correct
21 Correct 432 ms 34312 KB Output is correct
22 Correct 430 ms 34164 KB Output is correct
23 Correct 410 ms 34220 KB Output is correct
24 Correct 417 ms 34184 KB Output is correct