oj.uz

Submission #536573

# Submission time Handle Problem Language Result Execution time Memory
536573 2022-03-13T14:32:51 Z pokmui9909 Park (BOI16_park) C++17
0 / 100
 568 ms 66252 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));
    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 == 0 || i == V.size() - 1 || V[i].x != V[i - 1].x){
            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

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:24: 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 == 0 || i == V.size() - 1 || V[i].x != V[i - 1].x){
      |                      ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 66192 KB Output is correct
2 Correct 504 ms 66168 KB Output is correct
3 Correct 521 ms 66252 KB Output is correct
4 Correct 512 ms 66132 KB Output is correct
5 Correct 506 ms 66212 KB Output is correct
6 Correct 502 ms 66196 KB Output is correct
7 Correct 500 ms 66180 KB Output is correct
8 Incorrect 568 ms 66200 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1492 KB Output is correct
2 Correct 44 ms 1492 KB Output is correct
3 Correct 45 ms 1492 KB Output is correct
4 Correct 51 ms 1492 KB Output is correct
5 Correct 50 ms 1492 KB Output is correct
6 Incorrect 37 ms 1520 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 66192 KB Output is correct
2 Correct 504 ms 66168 KB Output is correct
3 Correct 521 ms 66252 KB Output is correct
4 Correct 512 ms 66132 KB Output is correct
5 Correct 506 ms 66212 KB Output is correct
6 Correct 502 ms 66196 KB Output is correct
7 Correct 500 ms 66180 KB Output is correct
8 Incorrect 568 ms 66200 KB Output isn't correct
9 Halted 0 ms 0 KB -