Submission #1172475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172475		VMaksimoski008	Park (BOI16_park)	C++20	100 / 100	520 ms	67892 KiB

park

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

struct union_find {
    int n;
    vector<int> par, size;

    union_find(int _n) : n(_n), par(n+1), size(n+1) {
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int u) {
        if(u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    void uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return ;
        if(size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        par[b] = a;
    }

    bool same_set(int a, int b) {
        return find(a) == find(b);
    }
};

double dist(ll x1, ll y1, ll x2, ll y2) {
    ll a = (x2 - x1) * (x2 - x1);
    ll b = (y2 - y1) * (y2 - y1);
    return sqrt(a + b);
}

vector<pii> bad[5][5];

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, q; cin >> n >> q;
    ll w, h; cin >> w >> h;

    bad[1][2] = bad[2][1] = {{n+3, n+4}, {n+1, n+3}, {n+2, n+3}};
    bad[1][3] = bad[3][1] = {{n+1, n+2}, {n+3, n+4}, {n+1, n+3}, {n+2, n+4}};
    bad[1][4] = bad[4][1] = {{n+1, n+2}, {n+1, n+3}, {n+1, n+4}};
    bad[2][3] = bad[3][2] = {{n+1, n+2}, {n+2, n+3}, {n+2, n+4}};
    bad[2][4] = bad[4][2] = {{n+1, n+2}, {n+3, n+4}, {n+2, n+3}, {n+1, n+4}};
    bad[3][4] = bad[4][3] = {{n+3, n+4}, {n+2, n+4}, {n+1, n+4}};

    vector<ar<ll, 3> > a(n+1);
    for(int i=1; i<=n; i++) cin >> a[i][0] >> a[i][1] >> a[i][2];

    vector<pair<double, pii> > E;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            double d = dist(a[i][0], a[i][1], a[j][0], a[j][1]);
            E.push_back({ d - a[i][2] - a[j][2], { i, j } });
        }

        E.push_back({ (double)a[i][0] - a[i][2], { i, n + 1 } });
        E.push_back({ (double)w - a[i][0] - a[i][2], { i, n + 2 } });
        E.push_back({ (double)a[i][1] - a[i][2], { i, n + 3 } });
        E.push_back({ (double)h - a[i][1] - a[i][2], { i, n + 4 } });
    }

    vector<ar<ll, 3> > qus(q+1);
    for(int i=1; i<=q; i++) {
        cin >> qus[i][0] >> qus[i][1];
        qus[i][2] = i;
    }

    sort(E.begin(), E.end());
    sort(qus.begin()+1, qus.end());

    vector<ar<int, 5> > ans(q+1);

    union_find dsu(n+4);
    int j = 0;
    for(int i=1; i<=q; i++) {
        auto [r, in, id] = qus[i];
        ans[id][in] = 1;
        while(j < E.size() && E[j].first < 2*r) {
            dsu.uni(E[j].second.first, E[j].second.second);
            j++;
        }

        for(int j=1; j<=4; j++) {
            bool ok = 1;
            for(auto [x, y] : bad[in][j])
                if(dsu.same_set(x, y)) ok = 0;
            ans[id][j] = ok;
        }
    }

    for(int i=1; i<=q; i++) {
        for(int j=1; j<=4; j++) if(ans[i][j]) cout << j;
        cout << '\n';
    }
}

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