Submission #1250567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250567		bruhhhh	Park (BOI16_park)	C++20	100 / 100	331 ms	49900 KiB

park

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll MOD = 1000000007;
const ll INF = 4e18;
ll z[4][4], f[4][4];
struct DSU {
    ll par[5000], sz[5000];
    DSU() {
        for (int i = 0; i < 5000; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }
    ll get(ll x) {
        return (par[x] == x ? x : par[x] = get(par[x]));
    }
    void cmb(ll x, ll y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return;
        }
        if (sz[x] < sz[y]) {
            swap(x, y);
        }
        par[y] = x;
        sz[x] += sz[y];
    }
};
ll cntdist(ll x, ll y){
    return floor(sqrtl(x * x + y * y));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, m, w, h;
    cin >> n >> m >> w >> h;
    vector<ll> a(n + 1), b(n + 1), c(n + 1);
    vector<array<ll, 3>> edges;
    for (int i = 0; i < 4; i++) {
        fill(z[i], z[i] + 4, INF);
        fill(f[i], f[i] + 4, INF);
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i];
        ll g = i + 4;
        for (int j = 0; j < i; j++){
            edges.push_back({cntdist(a[i] - a[j], b[i] - b[j]) - c[i] - c[j], g, j + 4});
        }
        edges.push_back({a[i] - c[i], 0, g});
        edges.push_back({b[i] - c[i], 1, g});
        edges.push_back({w - a[i] - c[i], 2, g});
        edges.push_back({h - b[i] - c[i], 3, g});
    }
    sort(edges.begin(), edges.end());
    DSU Wibu;
    for (auto &e : edges){
        Wibu.cmb(e[1], e[2]);
        for (int x = 0; x < 4; x++) {
            for (int y = 0; y < 4; y++) {
                if (Wibu.get(x) == Wibu.get(y)) {
                    z[x][y] = min(z[x][y], e[0]);
                }
            }
        }
    }
    auto add = [&](int u, int v, initializer_list<ll> vals) {
        ll mn = *min_element(vals.begin(), vals.end());
        f[u][v] = f[v][u] = mn;
    };
    add(0, 1, {z[1][3], z[1][0], z[1][2]});
    add(2, 3, {z[3][0], z[3][1], z[3][2]});
    add(0, 3, {z[0][1], z[0][2], z[0][3]});
    add(1, 2, {z[2][1], z[2][0], z[2][3]});
    add(0, 2, {z[1][3], z[0][2], z[0][1], z[2][3]});
    add(1, 3, {z[1][2], z[0][3], z[1][3], z[0][2]});
    while(m--){
        ll x, y;
        cin >> x >> y;
        y--;
        for (int i = 0; i < 4; i++){
            if (2 * x <= f[y][i]) {
                cout << i + 1;
            }
        }
        cout << '\n';
    }
    return 0;
}

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