Submission #536571

#	Time	Username	Problem	Language	Result	Execution time	Memory
536571		pokmui9909	Park (BOI16_park)	C++17	0 / 100	522 ms	66196 KiB

park

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

#define x first
#define y second
ll N, M, W, H;
pair<ll, ll> P[2500];
ll R[2500];
ll par[2500];
ll Find(ll n){
    if(par[n] < 0) return n;
    return par[n] = Find(par[n]);
}
void Union(ll a, ll b){
    a = Find(a), b = Find(b);
    if(a != b) par[a] += par[b], par[b] = a;
}
bool Same(ll a, ll b){
    return Find(a) == Find(b);
}
long double mxr[5][5];
long double dist(pair<ll, ll> a, pair<ll, ll> b){
    return sqrtl(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    memset(par, -1, sizeof(par));
    cin >> N >> M >> W >> H;
    for(int i = 0; i < N; i++){
        cin >> P[i].x >> P[i].y >> R[i];
    }
    vector<pair<long double, pair<ll, ll>>> V;
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j < N; j++){
            V.push_back(make_pair(dist(P[i], P[j]) - R[i] - R[j], make_pair(i, j)));
        }
        V.push_back(make_pair(P[i].y - R[i], make_pair(i, N)));
        V.push_back(make_pair(W - P[i].x - R[i], make_pair(i, N + 1)));
        V.push_back(make_pair(H - P[i].y - R[i], make_pair(i, N + 2)));
        V.push_back(make_pair(P[i].x - R[i], make_pair(i, N + 3)));
    }
    sort(V.begin(), V.end());
    for(int i = 0; i < V.size(); i++){
        if(i == V.size() - 1 || abs(V[i].x - V[i + 1].x) > 1e-6){
            if(!Same(N, N + 1) && !Same(N, N + 2) && !Same(N, N + 3)) mxr[0][1] = V[i].x / 2;
            if(!Same(N + 3, N) && !Same(N + 3, N + 1) && !Same(N + 2, N) && !Same(N + 2, N + 1)) mxr[0][2] = V[i].x / 2;
            if(!Same(N, N + 3) && !Same(N + 1, N + 3) && !Same(N + 2, N + 3)) mxr[0][3] = V[i].x / 2;
            if(!Same(N, N + 1) && !Same(N + 3, N + 1) && !Same(N + 2, N + 1)) mxr[1][2] = V[i].x / 2;
            if(!Same(N, N + 1) && !Same(N, N + 2) && !Same(N + 3, N + 1) && !Same(N + 3, N + 2)) mxr[1][3] = V[i].x / 2;
            if(!Same(N + 2, N) && !Same(N + 2, N + 1) && !Same(N + 2, N + 3)) mxr[2][3] = V[i].x / 2;
        }
        Union(V[i].y.x, V[i].y.y);
    }
    while(M--){
        ll r, e; cin >> r >> e; e--;
        for(ll i = 0; i < 4; i++){
            if(i == e || r < mxr[min(i, e)][max(i, e)]){
                cout << i + 1;
            }
        }
        cout << '\n';
    }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i < V.size(); i++){
      |                    ~~^~~~~~~~~~
park.cpp:47:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if(i == V.size() - 1 || abs(V[i].x - V[i + 1].x) > 1e-6){
      |            ~~^~~~~~~~~~~~~~~

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