제출 #1350032

#제출 시각아이디문제언어결과실행 시간메모리
1350032OwstinPark (BOI16_park)C++20
100 / 100
432 ms66316 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <utility>
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define pb push_back
#define all(x) begin(x), end(x)
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
#define double ld
class DSU{
    vector<int> pred;
    vector<int> sizes;
public:
    DSU(int size) : pred(size), sizes(size, 1){
        for (int i = 0; i < size; i++){
            pred[i] = i;
        }
    }
    int size(int x){
        return (pred[x] == x ? sizes[x] : sizes[x] = sizes[find(x)]);
    }
    int find(int x){
        return (pred[x] == x ? x : pred[x] = find(pred[x]));
    }
    bool unite(int x, int y){
        int xp = find(x);
        int yp = find(y);
        if (xp == yp){
            return false;
        }
        if (sizes[xp] < sizes[yp]){
            swap(xp, yp);
        }
        sizes[xp] += sizes[yp];
        pred[yp] = xp;
        return true;
    }
};
struct cow {
    double x, y, r;
};
struct edge {
    int x, y; double d;
};
bool cmp (const edge &x, const edge &y) {
    if (x.d != y.d) {
        return x.d < y.d;
    }
    if (x.x != y.x) {
        return x.x < y.x;
    }
    return x.y < y.y;
}
double dist(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
void solve() {
    int n, m, w, h; cin >> n >> m >> w >> h;
    vector<cow> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i].x >> vec[i].y >> vec[i].r;
    }
    vector<edge> edges;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            edges.pb({i, j, dist(vec[i].x, vec[i].y, vec[j].x, vec[j].y) - vec[i].r - vec[j].r});
        }
        edges.pb({i, n, dist(vec[i].x, vec[i].y, 0, vec[i].y) - vec[i].r});
        edges.pb({i, n + 1, dist(vec[i].x, vec[i].y, vec[i].x, 0) - vec[i].r});
        edges.pb({i, n + 2, dist(vec[i].x, vec[i].y, w, vec[i].y) - vec[i].r});
        edges.pb({i, n + 3, dist(vec[i].x, vec[i].y, vec[i].x, h) - vec[i].r});
    }
    sort(all(edges), cmp);
    DSU dsu(n + 4);
    vector<vector<double>> req(4, vector<double>(4, INT32_MAX));
    for (int i = 0; i < edges.size(); i++) {
        dsu.unite(edges[i].x, edges[i].y);
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                if (j == k) {
                    continue;
                }
                if (dsu.find(j + n) == dsu.find(k + n)) {
                    req[j][k] = min(req[j][k], edges[i].d);
                }
            }
        }
    }
    for (int i = 0; i < m; i++) {
        double r; int e; cin >> r >> e; e--;
        vector<int> can;
        if (!e) {
            can.pb(1);
            if (req[0][1] >= r * 2 && req[1][3] >= r * 2 && req[1][2] >= r * 2) {
                can.pb(2);
            }
            if (req[0][1] >= r * 2 && req[0][2] >= r * 2 && req[1][3] >= r * 2 && req[2][3] >= r * 2) {
                can.pb(3);
            }
            if (req[0][1] >= r * 2 && req[0][2] >= r * 2 && req[0][3] >= r * 2) {
                can.pb(4);
            }
        }
        else if (e == 1) {
            if (req[0][1] >= r * 2 && req[1][3] >= r * 2 && req[1][2] >= r * 2) {
                can.pb(1);
            }
            can.pb(2);
            if (req[1][2] >= r * 2 && req[0][2] >= r * 2 && req[2][3] >= r * 2) {
                can.pb(3);
            }
            if (req[1][2] >= r * 2 && req[0][2] >= r * 2 && req[1][3] >= r * 2 && req[0][3] >= r * 2) {
                can.pb(4);
            }
        }
        else if (e == 2) {
            if (req[0][1] >= r * 2 && req[0][2] >= r * 2 && req[1][3] >= r * 2 && req[2][3] >= r * 2) {
                can.pb(1);
            }
            if (req[1][2] >= r * 2 && req[0][2] >= r * 2 && req[2][3] >= r * 2) {
                can.pb(2);
            }
            can.pb(3);
            if (req[2][3] >= r * 2 && req[0][3] >= r * 2 && req[1][3] >= r * 2) {
                can.pb(4);
            }
        }
        else {
            if (req[0][1] >= r * 2 && req[0][2] >= r * 2 && req[0][3] >= r * 2) {
                can.pb(1);
            }
            if (req[1][2] >= r * 2 && req[0][2] >= r * 2 && req[1][3] >= r * 2 && req[0][3] >= r * 2) {
                can.pb(2);
            }
            if (req[2][3] >= r * 2 && req[0][3] >= r * 2 && req[1][3] >= r * 2) {
                can.pb(3);
            }
            can.pb(4);
        }
        for (auto x : can) {
            cout << x;
        }
        cout << '\n';
    }
}

int main() {
    FAST_IO;
    //freopen("skilevel.in", "r", stdin);
    //freopen("skilevel.out", "w", stdout);
    //TEST_CASES;
    solve(); //cout << endl;
    /*int a; cin >> a;
    for (int i = 1; i <= a; i++){
        cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }*/
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...