oj.uz

Submission #860363

# Submission time Handle Problem Language Result Execution time Memory
860363 2023-10-12T17:54:15 Z TahirAliyev Park (BOI16_park) C++17
100 / 100
 556 ms 74944 KB 
#include <bits/stdc++.h>

#define ll long long
#define int ll
#define pii pair<int, int>
#define double long double


using namespace std;

const int MAX1 = 2020, MAX2 = 1e5 + 5;

struct tree{
    double r; 
    int x, y;
};

struct edge{
    double r;
    int x, y;
};

int n, m, w, h;

tree trees[MAX1];

vector<edge> E;
vector<array<int, 3>> Q;

double dist(int x1, int y1, int x2, int y2){
    return sqrt(1ll * (x1 - x2) * (x1 - x2) + 1ll * (y1 - y2) * (y1 - y2));
}

int par[MAX1];
string ans[MAX2];

int get(int u){
    if(par[u] < 0) return u;
    return par[u] = get(par[u]);
}

bool con(int u, int v){
    return get(u) == get(v);
}

void unite(int u, int v){
    u = get(u);
    v = get(v);
    if(u == v) return;
    if(-par[u] < -par[v]){
        swap(u, v);
    }
    par[u] += par[v];
    par[v] = u;
}

bool comp(edge a, edge b){
    return a.r < b.r;
}

signed main(){
    memset(par, -1, sizeof(par));
    cin >> n >> m >> w >> h;
    for(int i = 1; i <= n; i++){
        int x, y, r; cin >> x >> y >> r;
        trees[i] = {1.0 * r, x, y};
    }
    for(int i = 1; i <= n; i++){
        E.push_back({1.0 * trees[i].x - trees[i].r, i, n + 1});
        E.push_back({1.0 * trees[i].y - trees[i].r, i, n + 2});
        E.push_back({1.0 * w - trees[i].x - trees[i].r, i, n + 3});
        E.push_back({1.0 * h - trees[i].y - trees[i].r, i, n + 4});
    }  
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            double d = dist(trees[i].x, trees[i].y, trees[j].x, trees[j].y);
            E.push_back({d - trees[i].r - trees[j].r, i, j});
        }
    }
    sort(E.begin(), E.end(), comp);
    for(int i = 1; i <= m; i++){
        int r, e; cin >> r >> e;
        Q.push_back({r, e, i});
    }
    sort(Q.begin(), Q.end());
    int id = 0;
    for(auto q : Q){
        while(id < E.size() && E[id].r < 2.0 * q[0]){
            unite(E[id].x, E[id].y);
            id++;
        }
        
        bool isB[5];
        isB[1] = con(n + 1, n + 2);
        isB[2] = con(n + 2, n + 3);
        isB[3] = con(n + 3, n + 4);
        isB[4] = con(n + 4, n + 1);
        bool hor = con(n + 1, n + 3);
        bool ver = con(n + 2, n + 4);
        if(isB[q[1]]){
            ans[q[2]] = '0' + q[1];
            continue;
        }
        string s = "";
        if(q[1] == 1){
            s += '1';
            if(!isB[2] && !ver) s += '2';
            if(!isB[3] && !ver && !hor) s += '3';
            if(!isB[4] && !hor) s += '4';
        }
        if(q[1] == 2){
            if(!isB[1] && !ver) s += '1';
            s += '2';
            if(!isB[3] && !hor) s += '3';
            if(!isB[4] && !ver && !hor) s += '4';
        }
        if(q[1] == 3){
            if(!isB[1] && !ver && !hor) s += '1';
            if(!isB[2] && !hor) s += '2';
            s += '3';
            if(!isB[4] && !ver) s += '4';
        }
        if(q[1] == 4){
            if(!isB[1] && !hor) s += '1';
            if(!isB[2] && !ver && !hor) s += '2';
            if(!isB[3] && !ver) s += '3';
            s += '4';
        }
        ans[q[2]] = s;
    }
    for(int i = 1; i <= m; i++){
        cout << ans[i] << '\n';
    }
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:88:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         while(id < E.size() && E[id].r < 2.0 * q[0]){
      |               ~~~^~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 71208 KB Output is correct
2 Correct 483 ms 70056 KB Output is correct
3 Correct 499 ms 69356 KB Output is correct
4 Correct 492 ms 70828 KB Output is correct
5 Correct 505 ms 70268 KB Output is correct
6 Correct 545 ms 70520 KB Output is correct
7 Correct 464 ms 71096 KB Output is correct
8 Correct 459 ms 69280 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 1 ms 3420 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8044 KB Output is correct
2 Correct 64 ms 8908 KB Output is correct
3 Correct 72 ms 9828 KB Output is correct
4 Correct 61 ms 10176 KB Output is correct
5 Correct 64 ms 10180 KB Output is correct
6 Correct 62 ms 9924 KB Output is correct
7 Correct 68 ms 8648 KB Output is correct
8 Correct 59 ms 8328 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 71208 KB Output is correct
2 Correct 483 ms 70056 KB Output is correct
3 Correct 499 ms 69356 KB Output is correct
4 Correct 492 ms 70828 KB Output is correct
5 Correct 505 ms 70268 KB Output is correct
6 Correct 545 ms 70520 KB Output is correct
7 Correct 464 ms 71096 KB Output is correct
8 Correct 459 ms 69280 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 1 ms 3420 KB Output is correct
11 Correct 66 ms 8044 KB Output is correct
12 Correct 64 ms 8908 KB Output is correct
13 Correct 72 ms 9828 KB Output is correct
14 Correct 61 ms 10176 KB Output is correct
15 Correct 64 ms 10180 KB Output is correct
16 Correct 62 ms 9924 KB Output is correct
17 Correct 68 ms 8648 KB Output is correct
18 Correct 59 ms 8328 KB Output is correct
19 Correct 543 ms 74592 KB Output is correct
20 Correct 543 ms 74136 KB Output is correct
21 Correct 556 ms 74944 KB Output is correct
22 Correct 548 ms 73280 KB Output is correct
23 Correct 545 ms 73440 KB Output is correct
24 Correct 522 ms 74648 KB Output is correct