oj.uz

Submission #1104725

# Submission time Handle Problem Language Result Execution time Memory
1104725 2024-10-24T09:31:10 Z tuannm Park (BOI16_park) C++17
100 / 100
 472 ms 70464 KB 
#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 2e3 + 5;
const string NAME = "escaping";
int n, m, w, h;
int p[N], ans[100001];

vector<tuple<int, int, int>> queries;
vector<tuple<long double, int, int>> edges;

int find_set(int u){
    if(u == p[u])
        return u;

    return p[u] = find_set(p[u]);
}

void join_set(int u, int v){
    u = find_set(u);
    v = find_set(v);

    if(u == v)
        return;

    p[v] = u;
}

struct circ{
    long double x, y, r;

    circ(long double _x = 0, long double _y = 0, long double _r = 0) : x(_x), y(_y), r(_r) {}
} a[N];

long double dis(int i, int j){
    long double gg = 1.0 * (a[i].x - a[j].x) * (a[i].x - a[j].x) + 1.0 * (a[i].y - a[j].y) * (a[i].y - a[j].y);
    gg = sqrtl(gg);

    gg -= 1.0 * (a[i].r + a[j].r);

    return gg;
}

bool ok(int i, int j){
    return find_set(i) != find_set(j);
}

bool check(int i, int j){
    if(i == j)
        return true;

    if(i > j)
        swap(i, j);

    if(i == 1 && j == 2)
        return (ok(n + 1, n + 2) && ok(n + 1, n + 3) && ok(n + 1, n + 4));

    if(i == 1 && j == 3)
        return (ok(n + 1, n + 3) && ok(n + 1, n + 4) && ok(n + 2, n + 3) && ok(n + 2, n + 4));

    if(i == 1 && j == 4)
        return (ok(n + 1, n + 4) && ok(n + 2, n + 4) && ok(n + 3, n + 4));

    if(i == 2 && j == 3)
        return (ok(n + 1, n + 2) && ok(n + 2, n + 3) && ok(n + 2, n + 4));

    if(i == 2 && j == 4)
        return (ok(n + 1, n + 2) && ok(n + 1, n + 3) && ok(n + 2, n + 4) && ok(n + 3, n + 4));

    return (ok(n + 1, n + 3) && ok(n + 2, n + 3) && ok(n + 3, n + 4));
}

void inp(){
    cin >> n >> m >> w >> h;

    for(int i = 1; i <= n; ++i){
        int x, y, r;
        cin >> x >> y >> r;

        a[i] = circ(x, y, r);
    }

    for(int i = 1; i <= m; ++i){
        int r, e;
        cin >> r >> e;

        queries.pb({r, e, i});
    }
}

void solve(){
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j){
            long double W = dis(i, j);

            edges.pb({W, i, j});
        }

    for(int i = 1; i <= n; ++i){
        long double W = (a[i].y <= a[i].r ? 0 : a[i].y - a[i].r);

        edges.pb({W, i, n + 1});
    }

    for(int i = 1; i <= n; ++i){
        long double W = (w - a[i].x <= a[i].r ? 0 : w - a[i].x - a[i].r);

        edges.pb({W, i, n + 2});
    }

    for(int i = 1; i <= n; ++i){
        long double W = (h - a[i].y <= a[i].r ? 0 : h - a[i].y - a[i].r);

        edges.pb({W, i, n + 3});
    }

    for(int i = 1; i <= n; ++i){
        long double W = (a[i].x <= a[i].r ? 0 : a[i].x - a[i].r);

        edges.pb({W, i, n + 4});
    }

    sort(edges.begin(), edges.end());
    sort(queries.begin(), queries.end());

    for(int i = 1; i <= n + 4; ++i)
        p[i] = i;

    int ptr = 0;
    for(auto [r, e, i] : queries){
        while(ptr < edges.size()){
            auto [W, u, v] = edges[ptr];
            if(W >= 2 * r)
                break;

            join_set(u, v);
            ++ptr;
        }

        for(int j = 1; j <= 4; ++j)
            if(check(e, j))
                ans[i] |= (1 << j);
    }

    for(int i = 1; i <= m; ++i){
        for(int j = 1; j <= 4; ++j)
            if((ans[i] >> j) & 1)
                cout << j;
        cout << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }

    inp();
    solve();
}

Compilation message

park.cpp: In function 'void solve()':
park.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long double, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         while(ptr < edges.size()){
      |               ~~~~^~~~~~~~~~~~~~
park.cpp: In function 'int main()':
park.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 68340 KB Output is correct
2 Correct 394 ms 68272 KB Output is correct
3 Correct 399 ms 68400 KB Output is correct
4 Correct 390 ms 68272 KB Output is correct
5 Correct 392 ms 68376 KB Output is correct
6 Correct 396 ms 68280 KB Output is correct
7 Correct 358 ms 68316 KB Output is correct
8 Correct 376 ms 68272 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4032 KB Output is correct
2 Correct 37 ms 4040 KB Output is correct
3 Correct 45 ms 4032 KB Output is correct
4 Correct 37 ms 4032 KB Output is correct
5 Correct 39 ms 4036 KB Output is correct
6 Correct 40 ms 4032 KB Output is correct
7 Correct 36 ms 2496 KB Output is correct
8 Correct 33 ms 2504 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 68340 KB Output is correct
2 Correct 394 ms 68272 KB Output is correct
3 Correct 399 ms 68400 KB Output is correct
4 Correct 390 ms 68272 KB Output is correct
5 Correct 392 ms 68376 KB Output is correct
6 Correct 396 ms 68280 KB Output is correct
7 Correct 358 ms 68316 KB Output is correct
8 Correct 376 ms 68272 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 38 ms 4032 KB Output is correct
12 Correct 37 ms 4040 KB Output is correct
13 Correct 45 ms 4032 KB Output is correct
14 Correct 37 ms 4032 KB Output is correct
15 Correct 39 ms 4036 KB Output is correct
16 Correct 40 ms 4032 KB Output is correct
17 Correct 36 ms 2496 KB Output is correct
18 Correct 33 ms 2504 KB Output is correct
19 Correct 450 ms 70376 KB Output is correct
20 Correct 472 ms 70308 KB Output is correct
21 Correct 460 ms 70364 KB Output is correct
22 Correct 454 ms 70308 KB Output is correct
23 Correct 461 ms 70360 KB Output is correct
24 Correct 425 ms 70464 KB Output is correct