Submission #1066912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066912		thinknoexit	Park (BOI16_park)	C++17	100 / 100	624 ms	35432 KiB

park

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2020;
struct Edge {
    int u, v;
    ll w;
    bool operator < (const Edge& o) const {
        return w < o.w;
    }
};
ll res[5][5];
ll x[N], y[N], r[N];
int n, m, p[N];
ll w, h;
ll sqrtt(ll x) {
    ll h = sqrt(x);
    while ((h + 1) * (h + 1) <= x) h++;
    while (h * h > x) h--;
    return h;
}
ll dis(int i, int j) {
    return sqrtt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]))
        - r[i] - r[j];
}
ll dis(int i, ll x1, ll y1) {
    return sqrtt((x[i] - x1) * (x[i] - x1) + (y[i] - y1) * (y[i] - y1))
        - r[i];
}
int fr(int i) {
    return p[i] == i ? i : p[i] = fr(p[i]);
}
void cut(ll w, vector<int> a, vector<int> b) {
    for (auto& x : a) for (auto& y : b)
        res[x][y] = min(res[x][y], w), res[y][x] = min(res[y][x], w);
}
void trycheck(ll w) {
    if (fr(n + 1) == fr(n + 2)) cut(w, { 1, 4 }, { 2, 3 });
    if (fr(n + 1) == fr(n + 3)) cut(w, { 1 }, { 2, 3, 4 });
    if (fr(n + 1) == fr(n + 4)) cut(w, { 2 }, { 1, 3, 4 });
    if (fr(n + 2) == fr(n + 3)) cut(w, { 4 }, { 1, 2, 3 });
    if (fr(n + 2) == fr(n + 4)) cut(w, { 3 }, { 1, 2, 4 });
    if (fr(n + 3) == fr(n + 4)) cut(w, { 1, 2 }, { 3, 4 });
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> w >> h;
    for (int i = 1;i <= n;i++) {
        cin >> x[i] >> y[i] >> r[i];
    }
    for (int i = 1;i <= n + 4;i++) p[i] = i;
    vector<Edge> e;
    for (int i = 1;i <= n;i++) {
        for (int j = i + 1;j <= n;j++) {
            e.push_back({ i, j, dis(i, j) });
        }
        // connect with fence
        e.push_back({ i, n + 1, dis(i, x[i], 0) }); // <-
        e.push_back({ i, n + 2, dis(i, x[i], h) }); // ->
        e.push_back({ i, n + 3, dis(i, 0, y[i]) }); // ^
        e.push_back({ i, n + 4, dis(i, w, y[i]) }); // v
    }
    memset(res, 0x3f, sizeof res);
    sort(e.begin(), e.end());
    for (auto& x : e) {
        p[fr(x.u)] = fr(x.v);
        trycheck(x.w);
    }
    while (m--) {
        int r, e;
        cin >> r >> e;
        r *= 2;
        for (int j = 1;j <= 4;j++) if (r <= res[e][j]) {
            cout << j;
        }
        cout << '\n';
    }
    return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

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