Submission #714900

#	Time	Username	Problem	Language	Result	Execution time	Memory
714900		Stickfish	Park (BOI16_park)	C++17	100 / 100	499 ms	41020 KiB

park

#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;

struct point {
    ll x;
    ll y;

    point() {}

    point(ll x_, ll y_): x(x_), y(y_) {}

    point operator-(const point pt) const {
        return {x - pt.x, y - pt.y};
    }

    ll sqlen() {
        return x * x + y * y;
    }
};

struct circle {
    point center;
    ll r;
};

struct dsu {
    void resize(int n) {
        rt.resize(n);
        sz.assign(n, 1);
        for (int i = 0; i < n; ++i)
            rt[i] = i;
    }

    int gst(int i) {
        if (rt[i] == i)
            return i;
        return rt[i] = gst(rt[i]);
    }

    void unite(int i, int j) {
        i = gst(i);
        j = gst(j);
        if (i == j)
            return;
        if (sz[i] < sz[j])
            swap(i, j);
        rt[j] = i;
        sz[i] += sz[j];
    }

    int size() {
        return rt.size();
    }
 private:
     vector<int> rt;
     vector<int> sz;
};

const int MAXN = 2001;
circle t[MAXN];

dsu get_dsu(int n, vector<pair<ll, pair<int, int>>>& edges, ll w) {
    dsu su;
    su.resize(n);
    for (auto p : edges) {
        if (p.first <= w) {
            su.unite(p.second.first, p.second.second);
        }
    }
    return su;
}

signed main() {
    int n, m;
    cin >> n >> m;
    ll w, h;
    cin >> w >> h;
    for (int i = 0; i < n; ++i) {
        cin >> t[i].center.x >> t[i].center.y >> t[i].r;
    }
    vector<pair<ll, pair<int, int>>> edges;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            // r[i] + r[j] + w >= dist(i, j)
            ll w = sqrtl((t[i].center - t[j].center).sqlen()) - t[i].r - t[j].r + 1;
            edges.push_back({w, {i, j}});
        }
        edges.push_back({t[i].center.x - t[i].r + 1, {i, n}});
        edges.push_back({t[i].center.y - t[i].r + 1, {i, n + 1}});
        edges.push_back({w - t[i].center.x - t[i].r + 1, {i, n + 2}});
        edges.push_back({h - t[i].center.y - t[i].r + 1, {i, n + 3}});
    }
    sort(edges.begin(), edges.end());
    //for (auto [w, e] : edges) {
        //cout << w << ": " << e.first + 1 << ' ' << (e.second < n ? e.second + 1 : n - e.second - 1) << endl;
    //}
    vector<pair<ll, int>> vis(m);
    vector<ll> visr(m);
    for (int i = 0; i < m; ++i) {
        cin >> vis[i].first >> vis[i].second;
        vis[i].first *= 2;
        visr[i] = vis[i].first;
    }
    sort(visr.begin(), visr.end());
    vector<dsu> sus(m);
    vector<int> wblock(6);
    for (int p = 0; p < 6; ++p) {
        int lb = -1, ub = m;
        while (ub - lb > 1) {
            int mb = (lb + ub) / 2;
            if (sus[mb].size() == 0)
                sus[mb] = get_dsu(n + 4, edges, visr[mb]);
            bool islinked;
            if (p < 4) {
                islinked = sus[mb].gst(n + p) == sus[mb].gst(n + (p + 1) % 4);
            } else if (p == 4) {
                islinked = sus[mb].gst(n) == sus[mb].gst(n + 2);
            } else {
                islinked = sus[mb].gst(n + 1) == sus[mb].gst(n + 3);
            }
            if (islinked)
                ub = mb;
            else
                lb = mb;
        }
        wblock[p] = ub;
    }
    //visr.push_back(228);
    //for (int i = 0; i < 6; ++i) {
        //cout << visr[wblock[i]] << ' ';
    //}
    //cout << endl;
    for (auto [r, c] : vis) {
        --c;
        bitset<6> blocks;
        int wi = lower_bound(visr.begin(), visr.end(), r) - visr.begin();
        for (int i = 0; i < 6; ++i)
            blocks[i] = wi >= wblock[i];

        bitset<4> ans;
        ans[c] = 1;
        for (int e = 0; e < 4; ++e) {
            if (blocks[e] || blocks[c])
                continue;
            if (((e ^ c) & 2) && blocks[4])
                continue;
            if ((__builtin_popcount(e) + __builtin_popcount(c)) % 2 && blocks[5])
                continue;
            ans[e] = 1;
        }
        for (int e = 0; e < 4; ++e) {
            if (ans[e])
                cout << e + 1;
        }
        cout << '\n';
    }
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42