oj.uz

Submission #1066756

# Submission time Handle Problem Language Result Execution time Memory
1066756 2024-08-20T06:25:36 Z vjudge1 Park (BOI16_park) C++17
0 / 100
 421 ms 69528 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using ld = long double;

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<ld,int,int>> d;
int dsu[mxN + 10];

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

string ans[mxM + 1];

ld dist(int i, int j) {
    return 1.0 * sqrt(1.0 * (x[i] - x[j]) * (x[i] - x[j]) + 1.0 * (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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 69276 KB Output is correct
2 Correct 414 ms 69276 KB Output is correct
3 Correct 416 ms 69488 KB Output is correct
4 Correct 421 ms 69272 KB Output is correct
5 Correct 412 ms 69280 KB Output is correct
6 Correct 419 ms 69276 KB Output is correct
7 Correct 381 ms 69308 KB Output is correct
8 Correct 387 ms 69528 KB Output is correct
9 Correct 2 ms 3416 KB Output is correct
10 Incorrect 1 ms 3420 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6872 KB Output is correct
2 Correct 37 ms 6864 KB Output is correct
3 Correct 35 ms 6960 KB Output is correct
4 Correct 29 ms 6876 KB Output is correct
5 Correct 34 ms 6816 KB Output is correct
6 Correct 30 ms 6876 KB Output is correct
7 Incorrect 28 ms 6232 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 69276 KB Output is correct
2 Correct 414 ms 69276 KB Output is correct
3 Correct 416 ms 69488 KB Output is correct
4 Correct 421 ms 69272 KB Output is correct
5 Correct 412 ms 69280 KB Output is correct
6 Correct 419 ms 69276 KB Output is correct
7 Correct 381 ms 69308 KB Output is correct
8 Correct 387 ms 69528 KB Output is correct
9 Correct 2 ms 3416 KB Output is correct
10 Incorrect 1 ms 3420 KB Output isn't correct
11 Halted 0 ms 0 KB -