Submission #1123892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123892		Zero_OP	Park (BOI16_park)	C++20	0 / 100	211 ms	24972 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; }

int 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;
        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 ";
        }
    };


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

        bool already_blocked = false;
        if(e == 1 && dsu.same_set(N, N + 1)) already_blocked = true;
        if(e == 2 && dsu.same_set(N, N + 3)) already_blocked = true;
        if(e == 3 && dsu.same_set(N + 3, N + 2)) already_blocked = true;
        if(e == 4 && dsu.same_set(N + 2, N + 1)) already_blocked = true;

        ans[id] = (1 << (e - 1));
        if(already_blocked){ //can't go out
            continue;
        }

        if(e == 1){
            if(!dsu.same_set(N, N + 2) && !dsu.same_set(N, N + 3)) ans[id] |= (1 << 1); //(1, 2)
            if(!dsu.same_set(N, N + 2) && !dsu.same_set(N + 2, N + 3) && !dsu.same_set(N + 1, N + 3)) ans[id] |= (1 << 2); //(1, 3)
            if(!dsu.same_set(N + 1, N + 3) && !dsu.same_set(N + 1, N + 2)) ans[id] |= (1 << 3); //(1, 4)
        }

        if(e == 2){
            if(!dsu.same_set(N, N + 2) && !dsu.same_set(N, N + 3)) ans[id] |= (1 << 0); //(1, 2)
            if(!dsu.same_set(N + 1, N + 3) && !dsu.same_set(N + 2, N + 2)) ans[id] |= (1 << 2); //(2, 3)
            if(!dsu.same_set(N, N + 2) && !dsu.same_set(N + 1, N + 2) && !dsu.same_set(N + 1, N + 3)) ans[id] |= (1 << 3); //(2, 4)
        }

        if(e == 3){
            if(!dsu.same_set(N, N + 2) && !dsu.same_set(N + 2, N + 3) && !dsu.same_set(N + 1, N + 3)) ans[id] |= (1 << 0); //(1, 3)
            if(!dsu.same_set(N + 1, N + 3) && !dsu.same_set(N + 2, N + 2)) ans[id] |= (1 << 1); //(2, 3)
            if(!dsu.same_set(N, N + 2) && !dsu.same_set(N + 2, N + 1)) ans[id] |= (1 << 3); //(3, 4)
        }

        if(e == 4){
            if(!dsu.same_set(N + 1, N + 3) && !dsu.same_set(N + 1, N + 2)) ans[id] |= (1 << 0); //(1, 4)
            if(!dsu.same_set(N, N + 2) && !dsu.same_set(N + 1, N + 2) && !dsu.same_set(N + 1, N + 3)) ans[id] |= (1 << 1); //(2, 4)
            if(!dsu.same_set(N, N + 2) && !dsu.same_set(N + 2, N + 1)) ans[id] |= (1 << 2); //(3, 4)
        }
    }

    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: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42