Submission #1211887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211887		madamadam3	Park (BOI16_park)	C++20	100 / 100	350 ms	72996 KiB

park

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define int long long int

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

struct Edge {
    int u, v; ld 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];
        }
    }
};

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

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

    // 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++) {
        edges.push_back(Edge {i, n+2, ld(h - (trees[i].y + trees[i].ir))});
        edges.push_back(Edge {i, n+0, ld(trees[i].y - trees[i].ir)});
        edges.push_back(Edge {i, n+3, ld(trees[i].x - trees[i].ir)});
        edges.push_back(Edge {i, n+1, ld(w - (trees[i].x + trees[i].ir))});

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

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

    vector<vector<bool>> answers(m, vector<bool>(4, true));
    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;
        queries[i].second--;
        queries[i].first *= 2;
    }

    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 && queries[remap[cq]].first <= el.w) {
            bool conn[4][4];

            for (int i = 0; i < 4; i++) {
                conn[i][i] = true;

                for (int j = i + 1; j < 4; j++) {
                    conn[i][j] = (dsu.find(n+i) == dsu.find(n+j));
                    conn[j][i] = conn[i][j];
                }
            }

            auto bad = [&](const int &x) { return conn[(x - 1 < 0 ? 3 : x - 1)][x]; };

            for (int i = 0; i < 4; i++) {
                if (queries[remap[cq]].second == i) { continue; }
                if (bad(queries[remap[cq]].second) || bad(i)) {
                    answers[remap[cq]][i] = false;
                    continue;
                }

                bool upok = conn[0][2];
                bool sok = conn[1][3];

                if (abs(queries[remap[cq]].second - i) == 2) {
                    if (upok || sok) {
                        answers[remap[cq]][i] = false;
                        continue;
                    }
                } else if (queries[remap[cq]].second + i == 3) {
                    if (sok) {
                        answers[remap[cq]][i] = false;
                        continue;
                    }
                } else {
                    if (upok) { answers[remap[cq]][i] = false; }
                }
            }

            ++cq;

            if (cq >= m) break;
        }

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

    // answer queries ...
    for (int i = 0; i < m; i++) {
        string ans = "";
        for (int j = 1; j <= 4; j++) {
            if (answers[i][j-1]) ans = ans + to_string(j);
        }
        cout << ans << "\n";
    }
    return 0;
}

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