Submission #1211851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211851		madamadam3	Park (BOI16_park)	C++20	0 / 100	158 ms	33440 KiB

park

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Circle {
    int x, y; // centre-point
    int rsq, ir; // radius squared, integer radius
};

struct Edge {
    int u, v; double w;
};

struct DSU {
    int n; vector<int> par, siz;

    DSU(int N) {
        n = N;
        par.resize(n); iota(par.begin(), par.end(), 0);
        siz.assign(n, 1);
    }

    int find(int v) {
        if (par[v] == v) return v;
        return par[v] = find(par[v]);
    }

    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) {
            if (siz[b] > siz[a]) swap(a, b);
            par[b] = a;
            siz[a] += siz[b];
        }
    }
};

void output_circle(Circle circle) {
    int x = circle.x, y = circle.y, rsq = circle.rsq;
    cout << "(x - (" << x << "))^2 + (y - (" << y << "))^2 = " << rsq << "\n";
}

void output_vertical_line(int x, int y1, int y2) {
    if (y2 < y1) swap(y1, y2);
    cout << "x = " << x << " \\left\\{" << y1 << " <= y <= " << y2 << "\\right\\}\n";
}

void output_horizontal_line(int y, int x1, int x2) {
    if (x2 < x1) swap(x1, x2);
    cout << "y = " << y << " \\left\\{" << x1 << " <= x <= " << x2 << "\\right\\}\n";
}

void output_join_line(Circle c1, Circle c2) {
    if (c1.x > c2.x) swap(c1, c2);
    int mp = c2.y - c1.y, mq = c2.x - c1.x;
    int cp = mp * c1.x;

    cout << "y = ";
    cout << "(" << mp << ") / (" << mq << ") * x ";
    cout << "+ (" << c1.y << " - (" << cp << ") / (" << mq << "))";

    string dx = to_string(mq), dy = to_string(mp);
    string r1 = to_string(c1.ir), r2 = to_string(c2.ir);
    string d = "((" + dx + ")^2+(" + dy + ")^2)^{0.5}";

    string lb = "(" + to_string(c1.x) + " + " + r1 + "*(" + dx + ")/(" + d + "))";
    string ub = "(" + to_string(c2.x) + " - " + r2 + "*(" + dx + ")/(" + d + "))";
    
    cout << " \\left\\{ " << lb << " <= x <= " << ub << "\\right\\}\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    // read n, m, w, h and the trees ...
    int n, m; cin >> n >> m;    
    int w, h; cin >> w >> h;

    // output_horizontal_line(0, 0, w);
    // output_horizontal_line(h, 0, w);
    // output_vertical_line(0, 0, h);
    // output_vertical_line(w, 0, h);

    vector<Circle> trees;
    for (int i = 0; i < n; i++) {
        int x, y, r; cin >> x >> y >> r;
        trees.push_back(Circle {x, y, r*r, r});
        output_circle(trees.back());
    }

    // preprocess ...

    // node n is top wall, n+1 is bottom wall, n+2 is left wall, n+3 is right wall
    vector<Edge> edges;
    for (int i = 0; i < n; i++) {
        // output_horizontal_line(trees[i].y, 0, trees[i].x - trees[i].ir);
        // output_horizontal_line(trees[i].y, trees[i].x + trees[i].ir, w);

        // output_vertical_line(trees[i].x, 0, trees[i].y - trees[i].ir);
        // output_vertical_line(trees[i].x, trees[i].y + trees[i].ir, h);

        edges.push_back(Edge {i, n, double(h - (trees[i].y + trees[i].ir))});
        edges.push_back(Edge {i, n+1, double(trees[i].y - trees[i].ir)});
        edges.push_back(Edge {i, n+2, double(trees[i].x - trees[i].ir)});
        edges.push_back(Edge {i, n+3, double(w - (trees[i].x + trees[i].ir))});

        for (int j = i + 1; j < n; j++) {
            // output_join_line(trees[i], trees[j]);
            int dx = trees[i].x - trees[j].x, dy = trees[i].y - trees[j].y;
            edges.push_back(Edge{i, j, sqrt(double(dx*dx+dy*dy)) - double(trees[i].ir) - double(trees[j].ir)});
        }
    }

    sort(edges.begin(), edges.end(), [](Edge &a, Edge &b) {
        return a.w < b.w;
    });

    vector<string> answers(m);
    vector<int> remap(m);
    vector<pair<int, int>> queries(m); // r, e
    for (int i = 0; i < m; i++) {
        cin >> queries[i].first >> queries[i].second;
    }

    iota(remap.begin(), remap.end(), 0);
    sort(remap.begin(), remap.end(), [&](int a, int b) {
        return queries[a].first < queries[b].first;
    });

    auto dsu = DSU(n+4);

    int cq = 0;
    for (auto &el : edges) {
        while (cq < m && el.w > 2 * queries[remap[cq]].first) {
            string ans = "";

            int t = dsu.find(n), b = dsu.find(n+1), l = dsu.find(n+2), r = dsu.find(n+3);
            bool closed[4] = {b == l, b == r, t == r, t == l};

            for (int i = 0; i < 4; i++) {
                if (i == queries[remap[cq]].second - 1) {
                    ans = ans + to_string(i+1);
                    continue;
                }

                if (!closed[queries[remap[cq]].second - 1] && !closed[i]) {
                    ans = ans + to_string(i+1);
                }
            }

            answers[remap[cq]] = ans;
            cq++;
        }

        dsu.unite(el.u, el.v);
    }

    while (cq < m) {
        string ans = "";

        int t = dsu.find(n), b = dsu.find(n+1), l = dsu.find(n+2), r = dsu.find(n+3);
        bool closed[4] = {b == l, b == r, t == r, t == l};

        for (int i = 0; i < 4; i++) {
            if (i == queries[remap[cq]].second - 1) {
                ans = ans + to_string(i+1);
                continue;
            }

            if (!closed[queries[remap[cq]].second - 1] && !closed[i]) {
                ans = ans + to_string(i+1);
            }
        }

        answers[remap[cq]] = ans;
        cq++;
    }

    // answer queries ...

    for (int i = 0; i < m; i++) {
        cout << answers[i] << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42