oj.uz

Submission #537108

# Submission time Handle Problem Language Result Execution time Memory
537108 2022-03-14T14:31:02 Z pokmui9909 Park (BOI16_park) C++17
100 / 100
 563 ms 66420 KB 
#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));
    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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 66160 KB Output is correct
2 Correct 530 ms 66196 KB Output is correct
3 Correct 524 ms 66148 KB Output is correct
4 Correct 531 ms 66164 KB Output is correct
5 Correct 534 ms 66112 KB Output is correct
6 Correct 519 ms 66184 KB Output is correct
7 Correct 518 ms 66196 KB Output is correct
8 Correct 510 ms 66328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1492 KB Output is correct
2 Correct 33 ms 1492 KB Output is correct
3 Correct 32 ms 1492 KB Output is correct
4 Correct 33 ms 1492 KB Output is correct
5 Correct 36 ms 1492 KB Output is correct
6 Correct 34 ms 1540 KB Output is correct
7 Correct 31 ms 1824 KB Output is correct
8 Correct 28 ms 1748 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 66160 KB Output is correct
2 Correct 530 ms 66196 KB Output is correct
3 Correct 524 ms 66148 KB Output is correct
4 Correct 531 ms 66164 KB Output is correct
5 Correct 534 ms 66112 KB Output is correct
6 Correct 519 ms 66184 KB Output is correct
7 Correct 518 ms 66196 KB Output is correct
8 Correct 510 ms 66328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 35 ms 1492 KB Output is correct
12 Correct 33 ms 1492 KB Output is correct
13 Correct 32 ms 1492 KB Output is correct
14 Correct 33 ms 1492 KB Output is correct
15 Correct 36 ms 1492 KB Output is correct
16 Correct 34 ms 1540 KB Output is correct
17 Correct 31 ms 1824 KB Output is correct
18 Correct 28 ms 1748 KB Output is correct
19 Correct 563 ms 66396 KB Output is correct
20 Correct 548 ms 66420 KB Output is correct
21 Correct 554 ms 66352 KB Output is correct
22 Correct 555 ms 66408 KB Output is correct
23 Correct 543 ms 66348 KB Output is correct
24 Correct 542 ms 66344 KB Output is correct