Submission #1301772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301772		sasde	Park (BOI16_park)	C++20	0 / 100	217 ms	28356 KiB

park

#include <bits/stdc++.h>
#define fi first
#define se second
#define nmax 100008

using namespace std;

typedef pair<int, int> pii;

struct pot {
    int x, y, r;
};

int n, m, w, h;
string ans[nmax];
pot a[2008];
vector<pair<int, pii> > edges, queries;

void make_edges() {
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int dx = a[i].x - a[j].x;
            int dy = a[i].y - a[j].y;
            long long dist_sq = (long long)dx * dx + (long long)dy * dy;
            int r_sum = a[i].r + a[j].r;
            int w = sqrtl(dist_sq) - r_sum;
            if (w < 0) {
                w = 0;
            }
            edges.push_back({w, {i, j}});
        }

        edges.push_back({max(0, a[i].x - a[i].r), {n + 4, i}});
        edges.push_back({max(0, h - a[i].y - a[i].r), {n + 3, i}});
        edges.push_back({max(0, w - a[i].x - a[i].r), {n + 2, i}});
        edges.push_back({max(0, a[i].y - a[i].r), {n + 1, i}});
    }
    sort(edges.begin(), edges.end());
}

struct dsu {
    int par[nmax];

    void init(int n) {
        for (int i = 1; i <= n; i++) {
            par[i] = -1;
        }
    }

    int root(int x) {
        return par[x] < 0 ? x : par[x] = root(par[x]);
    }

    bool join(int u, int v) {
        if ((u = root(u)) == (v = root(v))) {
            return false;
        }
        if (par[u] > par[v]) {
            swap(u, v);
        }
        par[u] += par[v];
        par[v] = u;
        return true;
    }

    bool check(int u, int v) {
        return root(u) == root(v);
    }    
}dsu;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> w >> h;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].r;
    }
    for (int i = 1; i <= m; i++) {
        int r, c;
        cin >> r >> c;
        queries.push_back({r, {c, i}});
    }
    sort(queries.begin(), queries.end());
    make_edges();
    dsu.init(n + 4);
    int idx = 0;
    for (pair<int, pii> query : queries) {
        int limit = query.fi * 2;
        int c = query.se.fi;
        int id = query.se.se;
        while (idx < (int)edges.size() && edges[idx].fi < limit) {
            dsu.join(edges[idx].se.fi, edges[idx].se.se);
            idx++;
        }
        string res = "";
        switch (c) {
            case 1: 
                if (dsu.check(n + 1, n + 4)) {
                    res = "1";
                }
                else {
                    res = "1";
                    if (!dsu.check(n + 1, n + 3)) {
                        res.push_back('2');
                    }
                    if (!dsu.check(n + 1, n + 3) and !dsu.check(n + 2, n + 4)) {
                        res.push_back('3');
                    }
                    if (!dsu.check(n + 2, n + 4)) {
                        res.push_back('4');
                    }
                }
                break;
            case 2:
                if (dsu.check(n + 1, n + 2)) {
                    res = "2";
                }
                else {
                    if (!dsu.check(n + 1, n + 3)) {
                        res.push_back('1');
                    }
                    res.push_back('2');
                    if (!dsu.check(n + 2, n + 4)) {
                        res.push_back('3');
                    }
                    if (!dsu.check(n + 2, n + 4) and !dsu.check(n + 1, n + 3)) {
                        res.push_back('4');
                    }
                }
                break;
            case 3:
                if (dsu.check(n + 2, n + 3)) {
                    res = "3";
                }
                else {
                    if (!dsu.check(n + 2, n + 4) and !dsu.check(n + 1, n + 3)) {
                        res.push_back('1');
                    }
                    if (!dsu.check(n + 2, n + 4)) {
                        res.push_back('2');
                    }
                    res.push_back('3');
                    if (!dsu.check(n + 1, n + 3)) {
                        res.push_back('4');
                    }
                }
                break;
            case 4:
                if (dsu.check(n + 4, n + 3)) {
                    res = "4";
                }
                else {
                    if (!dsu.check(n + 2, n + 4)) {
                        res.push_back('1');
                    }
                    if (!dsu.check(n + 2, n + 4) and !dsu.check(n + 1, n + 3)) {
                        res.push_back('2');
                    }
                    if (!dsu.check(n + 1, n + 3)) {
                        res.push_back('3');
                    }
                    res.push_back('4');
                }
                break;
            default:
                assert(false);
        }
        ans[id] = res;
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

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