제출 #1352473

#제출 시각아이디문제언어결과실행 시간메모리
1352473po_rag526Park (BOI16_park)C++17
0 / 100
2220 ms912 KiB
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p;
    DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) p[a] = b;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    int W, H;
    cin >> W >> H;

    vector<int> x(n), y(n), r(n);
    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i] >> r[i];

    while (m--) {
        int vr, entry;
        cin >> vr >> entry;

        // nodes: trees [0..n-1], walls [n..n+3]
        int LEFT = n, RIGHT = n+1, BOTTOM = n+2, TOP = n+3;

        DSU dsu(n + 4);

        // tree-tree connections
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long long dx = x[i] - x[j];
                long long dy = y[i] - y[j];
                long long dist2 = dx*dx + dy*dy;

                long long rr = (long long)(r[i] + vr) + (r[j] + vr);
                if (dist2 <= rr * rr) {
                    dsu.unite(i, j);
                }
            }
        }

        // tree-wall connections
        for (int i = 0; i < n; i++) {
            int rr = r[i] + vr;

            if (x[i] <= rr) dsu.unite(i, LEFT);
            if (W - x[i] <= rr) dsu.unite(i, RIGHT);
            if (y[i] <= rr) dsu.unite(i, BOTTOM);
            if (H - y[i] <= rr) dsu.unite(i, TOP);
        }

        vector<bool> ok(5, true); // 1..4

        // corner blocking
        if (dsu.find(LEFT) == dsu.find(BOTTOM)) ok[1] = false;
        if (dsu.find(BOTTOM) == dsu.find(RIGHT)) ok[2] = false;
        if (dsu.find(RIGHT) == dsu.find(TOP)) ok[3] = false;
        if (dsu.find(TOP) == dsu.find(LEFT)) ok[4] = false;

        // vertical barrier
        if (dsu.find(LEFT) == dsu.find(RIGHT)) {
            if (entry == 1 || entry == 2) {
                ok[3] = ok[4] = false;
            } else {
                ok[1] = ok[2] = false;
            }
        }

        // horizontal barrier
        if (dsu.find(TOP) == dsu.find(BOTTOM)) {
            if (entry == 1 || entry == 4) {
                ok[2] = ok[3] = false;
            } else {
                ok[1] = ok[4] = false;
            }
        }

        // output
        for (int i = 1; i <= 4; i++) {
            if (ok[i] || i == entry) cout << i;
        }
        cout << '\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...