제출 #1066775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1066775		vjudge1	Park (BOI16_park)	C++17	100 / 100	222 ms	40380 KiB

park

#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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42