Submission #86056

#	Time	Username	Problem	Language	Result	Execution time	Memory
86056		Flying_dragon_02	Park (BOI16_park)	C++14	100 / 100	647 ms	81048 KiB

park

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 2010;

int n, m, pSet[N];

long double x[N], y[N], r[N], side[N][N], ans[N][N];

long double w, h;

vector<pair<long double, ii>> edge;

long double dist(long double a, long double b) {
    return sqrtl(a * a + b * b);
}

int findSet(int u) {
    if(u == pSet[u]) return u;
    else return pSet[u] = findSet(pSet[u]);
}

void unionSet(int u, int v, long double len) {
    //cout << u << " " << v << "\n";
    u = findSet(u); v = findSet(v);
    if(u == v) return ;
    //cout << u << " " << v << "\n";
    for(int i = n + 1; i <= n + 4; i++) {
        if(findSet(i) != u) continue ;
        for(int j = n + 1; j <= n + 4; j++) {
            if(findSet(j) != v) continue ;
            //cout << i << " " << j << "\n";
            side[i - n][j - n] = len;
            side[j - n][i - n] = len;
        }
    }
    //cout << u << " " << v << "\n";
    pSet[u] = v;
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n >> m;
    cin >> w >> h;
    for(int i = 1; i <= n; i++)
        cin >> x[i] >> y[i] >> r[i];
    for(int i = 1; i <= n + 4; i++)
        pSet[i] = i;
    for(int i = 1; i <= n; i++) {
        long double lmao;
        for(int j = i + 1; j <= n; j++) {
            lmao = dist(x[i] - x[j], y[i] - y[j]) - r[i] - r[j];
            lmao /= 2.0;
            edge.pb({lmao, {i, j}});
        }
        lmao = (x[i] - r[i]) / 2.0;
        edge.pb({lmao, {i, n + 1}});
        lmao = (y[i] - r[i]) / 2.0;
        edge.pb({lmao, {i, n + 2}});
        lmao = (w - x[i] - r[i]) / 2.0;
        edge.pb({lmao, {i, n + 3}});
        lmao = (h - y[i] - r[i]) / 2.0;
        edge.pb({lmao, {i, n + 4}});
    }
    sort(edge.begin(), edge.end());
    for(int i = 0; i < edge.size(); i++) {
        //cout << edge[i].se.fi << " " << edge[i].se.se << "\n";
        unionSet(edge[i].se.fi, edge[i].se.se, edge[i].fi);
    }
    ans[1][2] = ans[2][1] = min(side[1][2], min(side[2][3], side[2][4]));
    ans[1][4] = ans[4][1] = min(side[1][2], min(side[1][4], side[1][3]));
    ans[2][3] = ans[3][2] = min(side[3][2], min(side[3][1], side[3][4]));
    ans[3][4] = ans[4][3] = min(side[4][2], min(side[4][3], side[4][1]));
    ans[1][3] = ans[3][1] = min(min(side[1][2], side[4][3]), min(side[1][3], side[4][2]));
    ans[2][4] = ans[4][2] = min(min(side[3][2], side[4][1]), min(side[1][3], side[4][2]));
    while(m--) {
        int r, e;
        cin >> r >> e;
        for(int i = 1; i <= 4; i++) {
            if(i == e || ans[e][i] >= r)
                cout << i;
        }
        cout << "\n";
    }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:74:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < edge.size(); i++) {
                    ~~^~~~~~~~~~~~~

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