oj.uz

Submission #1066775

# Submission time Handle Problem Language Result Execution time Memory
1066775 2024-08-20T06:55:39 Z vjudge1 Park (BOI16_park) C++17
100 / 100
 222 ms 40380 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr int mxN = 2'000;
constexpr int mxM = 100'000;

int n, m;
int w, h;
int x[mxN + 10], y[mxN + 10], r[mxN + 10];
vector<tuple<i64,int,int>> d;
int dsu[mxN + 10];

struct vis {
    int r, e, i;
} v[mxM + 1];

string ans[mxM + 1];

i64 dist(int i, int j) {
    return 1LL * sqrt(1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j])) - r[i] - r[j];
}

int getpar(int c) {
    if (dsu[c] < 0) return c;
    dsu[c] = getpar(dsu[c]);
    return dsu[c];
}

bool join(int i, int j) {
    i = getpar(i);
    j = getpar(j);
    if (i == j) return false;
    if (dsu[i] > dsu[j]) swap(i, j);
    dsu[i] += dsu[j];
    dsu[j] = i;
    return true;
}

vector<int> lc, rc;

bool isC(int num) {
    int i = getpar(lc[num]);
    int j = getpar(rc[num]);
    if (i == j) return true;
    return false;
}

bool check(int i, int j) {
    if (i == j) return true;
    if (i > j) swap(i, j);
    if (i == 1 && j == 2) {
        return !(isC(0) || isC(3) || isC(4));
    } else if (i == 1 && j == 3) {
        return !(isC(0) || isC(2) || isC(3) || isC(5));
    } else if (i == 1 && j == 4) {
        return !(isC(1) || isC(3) || isC(5));
    } else if (i == 2 && j == 3) {
        return !(isC(2) || isC(4) || isC(5));
    } else if (i == 2 && j == 4) {
        return !(isC(0) || isC(1) || isC(4) || isC(5));
    } else {
        return !(isC(0) || isC(1) || isC(2));
    }
}

void solve() {
    cin >> n >> m;
    cin >> w >> h;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> r[i];
    }

    for (int i = 0; i < m; i++) {
        cin >> v[i].r >> v[i].e;
        v[i].i = i;
    }

    sort(v, v + m, [](const auto i, const auto j) {
        return i.r < j.r;
    });

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            d.emplace_back(dist(i, j), i, j);
        }
    }

    for (int i = 0; i < n; i++) {
        d.emplace_back(y[i] - r[i], i, n);
        d.emplace_back(w - x[i] - r[i], i, n + 1);
        d.emplace_back(h - y[i] - r[i], i, n + 2);
        d.emplace_back(x[i] - r[i], i, n + 3);
    }

    sort(d.begin(), d.end());

    memset(dsu, -1, sizeof(dsu));
    lc = {n + 2, n + 2, n + 2, n, n, n + 3};
    rc = {n, n + 3, n + 1, n + 3, n + 1, n + 1};

    int id = 0;
    for (int i = 0; i < m; i++) {
        for (; id < (int) d.size() && get<0>(d[id]) < 2 * v[i].r; id++) {
            join(get<1>(d[id]), get<2>(d[id]));
        }
        ans[v[i].i] = "";
        for (int j = 1; j <= 4; j++) {
            if (check(v[i].e, j)) {
                ans[v[i].i] += (char) ('0' + j);
            }
        }
    }

    for (int i = 0; i < m; i++) {
        cout << ans[i] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tc = 1; 
    //cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 39624 KB Output is correct
2 Correct 179 ms 39616 KB Output is correct
3 Correct 209 ms 37576 KB Output is correct
4 Correct 204 ms 37572 KB Output is correct
5 Correct 177 ms 37572 KB Output is correct
6 Correct 186 ms 37572 KB Output is correct
7 Correct 169 ms 37576 KB Output is correct
8 Correct 172 ms 37572 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5512 KB Output is correct
2 Correct 28 ms 5496 KB Output is correct
3 Correct 43 ms 5500 KB Output is correct
4 Correct 31 ms 5344 KB Output is correct
5 Correct 27 ms 5344 KB Output is correct
6 Correct 26 ms 5584 KB Output is correct
7 Correct 39 ms 4948 KB Output is correct
8 Correct 37 ms 6224 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 39624 KB Output is correct
2 Correct 179 ms 39616 KB Output is correct
3 Correct 209 ms 37576 KB Output is correct
4 Correct 204 ms 37572 KB Output is correct
5 Correct 177 ms 37572 KB Output is correct
6 Correct 186 ms 37572 KB Output is correct
7 Correct 169 ms 37576 KB Output is correct
8 Correct 172 ms 37572 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 31 ms 5512 KB Output is correct
12 Correct 28 ms 5496 KB Output is correct
13 Correct 43 ms 5500 KB Output is correct
14 Correct 31 ms 5344 KB Output is correct
15 Correct 27 ms 5344 KB Output is correct
16 Correct 26 ms 5584 KB Output is correct
17 Correct 39 ms 4948 KB Output is correct
18 Correct 37 ms 6224 KB Output is correct
19 Correct 222 ms 38848 KB Output is correct
20 Correct 210 ms 40380 KB Output is correct
21 Correct 213 ms 38596 KB Output is correct
22 Correct 206 ms 38640 KB Output is correct
23 Correct 205 ms 38588 KB Output is correct
24 Correct 190 ms 38856 KB Output is correct