Submission #1162954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162954		nh0902	Park (BOI16_park)	C++20	0 / 100	249 ms	35704 KiB

park

#include <bits/stdc++.h>

using namespace std;

const int N = 2010;

const int M = 100005;

const int INF = 1e9 + 10;

const long long inf = 1e13;

const long long mod = 1e9 + 7;

const long long p2 = 31;

int n, m, t;

int sz[N], pa[N];

double max_r[5];

int find_anc(int x) {
    return x == pa[x] ? x : pa[x] = find_anc(pa[x]);
}

void join_set(int x, int y) {
    x = find_anc(x);
    y = find_anc(y);

    if (x == y) return;

    if (sz[x] < sz[y]) swap(x, y);

    sz[x] += sz[y];
    pa[y] = x;
}

int x[N], y[N], r[N];

int w, h;

struct Edge {
    int a, b;
    double d;
};

bool cmp(Edge e1, Edge e2) {
    return e1.d < e2.d;
}

double solve(double x, double y, double r) {
    return - sqrt((x + y + r) * (x + y + r) - x * x - y * y + r * r) + x + y + r;
}

double dis(int i, int j) {
    //cout << x[i] - x[j] << "\n";
    //cout << y[i] - y[j] << "\n";
    return sqrt((double) (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) - (double) r[i] - r[j];
}

vector<Edge> E;

vector<int> ans[M];

vector<array<int, 3>> query;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    cin >> w >> h;

    for (int i = 1; i <= 4; i ++) max_r[i] = (double) min(w, h) / 2;

    for (int i = 1; i <= n; i ++) {
        cin >> x[i] >> y[i] >> r[i];
        E.push_back({i, n + 1, y[i] - r[i]});
        E.push_back({i, n + 2, w - x[i] - r[i]});
        E.push_back({i, n + 3, h - y[i] - r[i]});
        E.push_back({i, n + 4, x[i] - r[i]});

        max_r[1] = min(max_r[1], solve(x[i], y[i], r[i]));
        max_r[2] = min(max_r[2], solve(w - x[i], y[i], r[i]));
        max_r[3] = min(max_r[3], solve(w - x[i], h - y[i], r[i]));
        max_r[4] = min(max_r[4], solve(x[i], h - y[i], r[i]));
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = i + 1; j <= n; j ++) {
            E.push_back({i, j, dis(i, j)});
            //cout << i << " - " << j << " : " << dis(i, j) << "\n";
        }
    }

    for (int i = 1; i <= 4; i ++) {
        //cout << max_r[i] << "\n";
    }

    //dis(3, 4);

    sort(E.begin(), E.end(), cmp);

    int a, b;
    for (int i = 1; i <= m; i ++) {
        cin >> a >> b;
        query.push_back({a, b, i});
    }

    sort(query.begin(), query.end());

    int cur_e = 0;

    for (int i = 1; i <= n + 4; i ++) {
        sz[i] = 1;
        pa[i] = i;
    }

    for (auto q : query) {
        auto [ra, en, id] = q;
        while (cur_e < E.size() && E[cur_e].d < (double) ra * 2) {
            //cout << id << " : " << E[cur_e].a << " - " << E[cur_e].b << " " << E[cur_e].d << "\n";
            join_set(E[cur_e].a, E[cur_e].b);
            cur_e ++;

        }

        //cout << id << "\n";

        if ((double) ra > max_r[en]) continue;

        int side[4];

        side[0] = en;
        for (int i = 1; i < 4; i ++) side[i] = side[i - 1] % 4 + 1;

        //cout << id << " : " << en << " : " << n + side[0] << " " << n + side[3] << "\n";

        ans[id].push_back(side[0]);

        if (find_anc(n + side[0]) == find_anc(n + side[3])) continue;

        bool c02 = find_anc(n + side[0]) != find_anc(n + side[2]);
        bool c01 = find_anc(n + side[0]) != find_anc(n + side[1]);

        bool c31 = find_anc(n + side[3]) != find_anc(n + side[1]);
        bool c32 = find_anc(n + side[3]) != find_anc(n + side[2]);

        bool c21 = find_anc(n + side[1]) != find_anc(n + side[2]);

        if (c02 && c01) ans[id].push_back(side[1]);
        if (c31 && c32) ans[id].push_back(side[3]);
        if (c02 && c31 && c21) ans[id].push_back(side[2]);

        sort(ans[id].begin(), ans[id].end());
    }

    for (int i = 1; i <= m; i ++) {
        for (int v : ans[i]) cout << v;
        cout << "\n";
    }

    return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:80:37: warning: narrowing conversion of '(y[i] - r[i])' from 'int' to 'double' [-Wnarrowing]
   80 |         E.push_back({i, n + 1, y[i] - r[i]});
      |                                ~~~~~^~~~~~
park.cpp:81:41: warning: narrowing conversion of '((w - x[i]) - r[i])' from 'int' to 'double' [-Wnarrowing]
   81 |         E.push_back({i, n + 2, w - x[i] - r[i]});
      |                                ~~~~~~~~~^~~~~~
park.cpp:82:41: warning: narrowing conversion of '((h - y[i]) - r[i])' from 'int' to 'double' [-Wnarrowing]
   82 |         E.push_back({i, n + 3, h - y[i] - r[i]});
      |                                ~~~~~~~~~^~~~~~
park.cpp:83:37: warning: narrowing conversion of '(x[i] - r[i])' from 'int' to 'double' [-Wnarrowing]
   83 |         E.push_back({i, n + 4, x[i] - r[i]});
      |                                ~~~~~^~~~~~

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