Submission #602345

#	Time	Username	Problem	Language	Result	Execution time	Memory
602345		ziduo	Park (BOI16_park)	C++14	100 / 100	559 ms	66452 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(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    
    memset(par, -1, sizeof(par));
    for(int i = 0; i < 5; i++) for(int j = 0; j < 5; j++) mxr[i][j] = 1e18;
    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++){
        Union(V[i].y.x, V[i].y.y);
        while(i < V.size() - 1 && abs(V[i].x - V[i + 1].x) <= 1e-6){
            i++;
            Union(V[i].y.x, V[i].y.y);
        }
        if(Same(N, N + 1) || Same(N, N + 2) || Same(N, N + 3)) mxr[0][1] = min(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] = min(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] = min(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] = min(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] = min(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] = min(mxr[2][3], V[i].x / 2);
    }
    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)] <= 1e-6){
                cout << i + 1;
            }
        }
        cout << '\n';
    }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:47: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]
   47 |     for(int i = 0; i < V.size(); i++){
      |                    ~~^~~~~~~~~~
park.cpp:49:17: 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]
   49 |         while(i < V.size() - 1 && abs(V[i].x - V[i + 1].x) <= 1e-6){
      |               ~~^~~~~~~~~~~~~~

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