Submission #1163065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163065		nh0902	Park (BOI16_park)	C++20	100 / 100	515 ms	70432 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;

#define double long double

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

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

double 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((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) - 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);
    
    /*
    x[1] = 2.0;
    x[2] = 5.0;
    y[1] = 2.0;
    y[2] = 6.0;
    cout << dis(1, 2) << "\n";
    */
    
    cin >> n >> m;

    cin >> w >> h;

    for (int i = 1; i <= 4; i ++) max_r[i] = 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";
        }
    }

    E.push_back({n + 1, n + 3, h});
    E.push_back({n + 2, n + 4, w});

    //dis(3, 4);

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

    double 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) {
        double ra = q[0];
        int en = q[1];
        int id = q[2];
        while (cur_e < E.size() && E[cur_e].d < ra * 2.0) {
            //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";

        int j = id;

        ans[j].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[j].push_back(side[1]);
        if (c31 && c32) ans[j].push_back(side[3]);
        if (c02 && c31 && c21) ans[j].push_back(side[2]);

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


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

    return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:118:26: warning: narrowing conversion of 'a' from 'long double' to 'int' [-Wnarrowing]
  118 |         query.push_back({a, b, i});
      |                          ^
park.cpp:118:29: warning: narrowing conversion of 'b' from 'long double' to 'int' [-Wnarrowing]
  118 |         query.push_back({a, b, i});
      |                             ^

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