Submission #1012862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012862		imann	Park (BOI16_park)	C++17	0 / 100	282 ms	35264 KiB

park

#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<int, 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;
        int 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: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42