Submission #1137080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137080		anonymous321	Park (BOI16_park)	C++20	100 / 100	426 ms	40764 KiB

park

// https://oj.uz/problem/view/BOI16_park
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> p;

int find (int v) {
    if (p[v] == v) return v;
    p[v] = find(p[v]);
    return p[v];
}

void uni (int v1, int v2) {
    int r1 = find(v1);
    int r2 = find(v2);
    p[r2] = r1;
}

int main() {
    int n, m;
    cin >> n >> m;
    ll w, h;
    cin >> w >> h;
    vector<ll> tx (n);
    vector<ll> ty (n);
    vector<ll> tr (n);
    for (int i = 0; i < n; i++) {
        cin >> tx[i] >> ty[i] >> tr[i];
    }
    vector<tuple<ll, int, int>> v (m);
    for (int i = 0; i < m; i++) {
        ll r;
        int e;
        cin >> r >> e;
        v[i] = {r, e-1, i};
    }
    sort(v.begin(), v.end());

    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> q {};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            ll dx = tx[i] - tx[j];
            ll dy = ty[i] - ty[j];
            double d = sqrt(dx*dx + dy*dy);
            d -= tr[i] + tr[j];
            q.push({d, i, j});
        }
    }
    for (int i = 0; i < n; i++) {
        double d1 = tx[i] - tr[i];
        double d2 = ty[i] - tr[i];
        double d3 = w - tx[i] - tr[i];
        double d4 = h - ty[i] - tr[i];
        q.push({d1, i, n});
        q.push({d2, i, n+1});
        q.push({d3, i, n+2});
        q.push({d4, i, n+3});
    }
    
    p = vector<int> (n+4);
    for (int i = 0; i < n+4; i++) {
        p[i] = i;
    }
    vector<vector<bool>> sol (m, vector<bool>(4, true));
    for (int i = 0; i < m; i++) {
        auto[r, e, id] = v[i];
        while (!q.empty() && get<0>(q.top()) < 2*r) {
            auto[d, v1, v2] = q.top();
            q.pop();
            uni(v1, v2);
        }
        vector<int> w {find(n), find(n+1), find(n+2), find(n+3)};
        if (w[(e+1) % 4] == w[e]) {
            sol[id][(e+1) % 4] = false;
            sol[id][(e+2) % 4] = false;
            sol[id][(e+3) % 4] = false;
        }
        if (w[(e+1) % 4] == w[(e+3) % 4]) {
            sol[id][(e+1) % 4] = false;
            sol[id][(e+2) % 4] = false;
        }
        if (w[(e+1) % 4] == w[(e+2) % 4]) {
            sol[id][(e+1) % 4] = false;
        }
        if (w[e] == w[(e+2) % 4]) {
            sol[id][(e+2) % 4] = false;
            sol[id][(e+3) % 4] = false;
        }
        if (w[e] == w[(e+3) % 4]) {
            sol[id][(e+3) % 4] = false;
        }
        if (w[(e+2) % 4] == w[(e+3) % 4]) {
            sol[id][(e+2) % 4] = false;
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 4; j++) {
            if (sol[i][j]) cout << j+1;
        }
        cout << "\n";
    }
    return 0;
}

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