Submission #1123897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123897		Zero_OP	Park (BOI16_park)	C++20	100 / 100	248 ms	26388 KiB

park

#include <bits/stdc++.h>

using namespace std;

struct circle{
    int x, y, r;
    circle() : x(0), y(0), r(0) {}
    circle(int x, int y, int r) : x(x), y(y), r(r) {}

    friend istream& operator >> (istream& in, circle& c){
        return in >> c.x >> c.y >> c.r;
    }
};

struct query{
    int e, r, id;
    query(int e, int r, int id) : e(e), r(r), id(id) {}
    bool operator < (const query& o){ return r < o.r; }
};

struct edge{
    int w, u, v;
    edge(int w, int u, int v) : w(w), u(u), v(v) {}

    bool operator < (const edge& o){ return w < o.w; }
};

struct disjoint_set_union{
    vector<int> lab;
    disjoint_set_union(int n) : lab(n, -1) {}

    int root(int u){
        return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
    }

    bool join(int u, int v){
        u = root(u);
        v = root(v);
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }

    bool same_set(int u, int v){ return root(u) == root(v); }
};

long long sqr(long long x){ return x * x; }

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, Q, w, h;
    cin >> N >> Q >> w >> h;

    vector<circle> circles(N);
    for(int i = 0; i < N; ++i) cin >> circles[i];

    vector<query> queries;
    for(int i = 0; i < Q; ++i){
        int r, e;
        cin >> r >> e;
        r *= 2;
        queries.push_back(query(e, r, i));
    }

    vector<edge> edges;

    for(int i = 0; i < N; ++i){
        int x = circles[i].x, y = circles[i].y, r = circles[i].r;
        //bottom
        int d1 = y - r;
        edges.push_back(edge(d1, N, i));
        //left
        int d2 = x - r;
        edges.push_back(edge(d2, N + 1, i));
        //top
        int d3 = (h - y) - r;
        edges.push_back(edge(d3, N + 2, i));
        //right
        int d4 = (w - x) - r;
        edges.push_back(edge(d4, N + 3, i));
    }

    for(int i = 0; i < N; ++i){
        for(int j = i + 1; j < N; ++j){
            int d = sqrt(sqr(circles[i].x - circles[j].x) + sqr(circles[i].y - circles[j].y)) - circles[i].r - circles[j].r;
            edges.push_back(edge(d, i, j));
        }
    }

    sort(edges.begin(), edges.end());
    sort(queries.begin(), queries.end());

    auto output = [&](int x){
        if(x < N) cout << x << ' ';
        else{
            if(x == N) cout << "bottom ";
            if(x == N + 1) cout << "left ";
            if(x == N + 2) cout << "top ";
            if(x == N + 3) cout << "right ";
        }
    };


#define bottom (N)
#define left (N + 1)
#define top (N + 2)
#define right (N + 3)

    vector<int> ans(Q);
    disjoint_set_union dsu(N + 4);

    auto is_blocked = [&](int i){
        if(i == 1) return dsu.same_set(bottom, left);
        if(i == 2) return dsu.same_set(bottom, right);
        if(i == 3) return dsu.same_set(top, right);
        if(i == 4) return dsu.same_set(top, left);
        assert(false);
    };

    auto check = [&](int s, int t) -> bool{
        if(s == t) return true;
        if(is_blocked(s) || is_blocked(t)) return false;
        if(s > t) swap(s, t);
        if(s == 1){
            if(t == 2) return !dsu.same_set(bottom, top);
            if(t == 3) return !dsu.same_set(bottom, top) && !dsu.same_set(left, right);
            if(t == 4) return !dsu.same_set(left, right);
            assert(1 == 0);
        } else if(s == 2){
            if(t == 3) return !dsu.same_set(left, right);
            if(t == 4) return !dsu.same_set(bottom, top) && !dsu.same_set(left, right);
            assert(2 == 0);
        } else if(s == 3){
            if(t == 4) return !dsu.same_set(bottom, top);
            assert(3 == 0);
        }
        assert(4 == 0);
    };

    int i = 0;
    for(auto [e, r, id] : queries){
        while(i < (int)edges.size() && edges[i].w < r){
            dsu.join(edges[i].u, edges[i].v);
            ++i;
        }

        for(int i = 1; i <= 4; ++i){
            if(check(e, i)){
                ans[id] |= (1 << (i - 1));
            }
        }
    }

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

    return 0;
}

/*

Note :
- 1 : bottom left
- 2 : bottom right
- 3 : top right
- 4 : top left

- N : bottom
- N + 1 : left
- N + 2 : top
- N + 3 : right

*/

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