oj.uz

Submission #1066912

# Submission time Handle Problem Language Result Execution time Memory
1066912 2024-08-20T08:43:42 Z thinknoexit Park (BOI16_park) C++17
100 / 100
 624 ms 35432 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2020;
struct Edge {
    int u, v;
    ll w;
    bool operator < (const Edge& o) const {
        return w < o.w;
    }
};
ll res[5][5];
ll x[N], y[N], r[N];
int n, m, p[N];
ll w, h;
ll sqrtt(ll x) {
    ll h = sqrt(x);
    while ((h + 1) * (h + 1) <= x) h++;
    while (h * h > x) h--;
    return h;
}
ll dis(int i, int j) {
    return sqrtt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]))
        - r[i] - r[j];
}
ll dis(int i, ll x1, ll y1) {
    return sqrtt((x[i] - x1) * (x[i] - x1) + (y[i] - y1) * (y[i] - y1))
        - r[i];
}
int fr(int i) {
    return p[i] == i ? i : p[i] = fr(p[i]);
}
void cut(ll w, vector<int> a, vector<int> b) {
    for (auto& x : a) for (auto& y : b)
        res[x][y] = min(res[x][y], w), res[y][x] = min(res[y][x], w);
}
void trycheck(ll w) {
    if (fr(n + 1) == fr(n + 2)) cut(w, { 1, 4 }, { 2, 3 });
    if (fr(n + 1) == fr(n + 3)) cut(w, { 1 }, { 2, 3, 4 });
    if (fr(n + 1) == fr(n + 4)) cut(w, { 2 }, { 1, 3, 4 });
    if (fr(n + 2) == fr(n + 3)) cut(w, { 4 }, { 1, 2, 3 });
    if (fr(n + 2) == fr(n + 4)) cut(w, { 3 }, { 1, 2, 4 });
    if (fr(n + 3) == fr(n + 4)) cut(w, { 1, 2 }, { 3, 4 });
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> w >> h;
    for (int i = 1;i <= n;i++) {
        cin >> x[i] >> y[i] >> r[i];
    }
    for (int i = 1;i <= n + 4;i++) p[i] = i;
    vector<Edge> e;
    for (int i = 1;i <= n;i++) {
        for (int j = i + 1;j <= n;j++) {
            e.push_back({ i, j, dis(i, j) });
        }
        // connect with fence
        e.push_back({ i, n + 1, dis(i, x[i], 0) }); // <-
        e.push_back({ i, n + 2, dis(i, x[i], h) }); // ->
        e.push_back({ i, n + 3, dis(i, 0, y[i]) }); // ^
        e.push_back({ i, n + 4, dis(i, w, y[i]) }); // v
    }
    memset(res, 0x3f, sizeof res);
    sort(e.begin(), e.end());
    for (auto& x : e) {
        p[fr(x.u)] = fr(x.v);
        trycheck(x.w);
    }
    while (m--) {
        int r, e;
        cin >> r >> e;
        r *= 2;
        for (int j = 1;j <= 4;j++) if (r <= res[e][j]) {
            cout << j;
        }
        cout << '\n';
    }
    return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 34492 KB Output is correct
2 Correct 591 ms 34240 KB Output is correct
3 Correct 594 ms 33476 KB Output is correct
4 Correct 606 ms 35016 KB Output is correct
5 Correct 608 ms 33980 KB Output is correct
6 Correct 585 ms 33736 KB Output is correct
7 Correct 328 ms 35272 KB Output is correct
8 Correct 332 ms 34848 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2000 KB Output is correct
2 Correct 25 ms 2004 KB Output is correct
3 Correct 24 ms 2000 KB Output is correct
4 Correct 25 ms 2024 KB Output is correct
5 Correct 25 ms 1980 KB Output is correct
6 Correct 27 ms 2012 KB Output is correct
7 Correct 25 ms 1372 KB Output is correct
8 Correct 19 ms 1372 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 34492 KB Output is correct
2 Correct 591 ms 34240 KB Output is correct
3 Correct 594 ms 33476 KB Output is correct
4 Correct 606 ms 35016 KB Output is correct
5 Correct 608 ms 33980 KB Output is correct
6 Correct 585 ms 33736 KB Output is correct
7 Correct 328 ms 35272 KB Output is correct
8 Correct 332 ms 34848 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 26 ms 2000 KB Output is correct
12 Correct 25 ms 2004 KB Output is correct
13 Correct 24 ms 2000 KB Output is correct
14 Correct 25 ms 2024 KB Output is correct
15 Correct 25 ms 1980 KB Output is correct
16 Correct 27 ms 2012 KB Output is correct
17 Correct 25 ms 1372 KB Output is correct
18 Correct 19 ms 1372 KB Output is correct
19 Correct 611 ms 35432 KB Output is correct
20 Correct 615 ms 35264 KB Output is correct
21 Correct 624 ms 34756 KB Output is correct
22 Correct 607 ms 33724 KB Output is correct
23 Correct 602 ms 33728 KB Output is correct
24 Correct 351 ms 33984 KB Output is correct