Submission #1355461

#TimeUsernameProblemLanguageResultExecution timeMemory
1355461gogohPark (BOI16_park)C++20
100 / 100
762 ms137492 KiB
#include<bits/stdc++.h>

int main(){
    std::cin.tie(nullptr)->std::ios_base::sync_with_stdio(false);

    int n, m, w, h;
    std::cin >> n >> m >> w >> h;
    std::vector<std::vector<int>> a(n+1, std::vector<int>(3));
    std::vector<std::vector<int>> q(m+1, std::vector<int>(3));
    for(int i=1; i<=n; i++)
        std::cin >> a[i][0] >> a[i][1] >> a[i][2];
    for(int i=1; i<=m; i++){
        std::cin >> q[i][0] >> q[i][1];
        q[i][2] = i;
    }
    std::sort(q.begin()+1, q.end());
    std::vector<std::tuple<long double, int, int>> edges;
    for(int i=1; i<=n; i++){
        edges.emplace_back((long double)(a[i][1] - a[i][2]), i, n + 1);
        edges.emplace_back((long double)(w - a[i][0] - a[i][2]), i, n + 2);
        edges.emplace_back((long double)(h - a[i][1] - a[i][2]), i, n + 3);
        edges.emplace_back((long double)(a[i][0] - a[i][2]), i, n + 4);
        for(int j=1; j<=n; j++){
            long long dx = a[i][0] - a[j][0];
            long long dy = a[i][1] - a[j][1];
            long double dist = sqrt(dx*dx + dy*dy);
            edges.emplace_back(dist - (long double)a[i][2] - (long double)a[j][2], i, j);
        }
    }
    std::sort(edges.begin(), edges.end());
    std::vector<int> parent(n+10);
    iota(parent.begin(), parent.end(), 0);
    auto find_parent = [&](auto &&find_parent, int u) -> int {
        if(parent[u] == u) return u;
        return parent[u] = find_parent(find_parent, parent[u]);
    };
    auto unite = [&](int u, int v) -> void {
        int a = find_parent(find_parent, u), b = find_parent(find_parent, v);
        if(a != b) parent[a] = b;
    };
    std::vector<std::string> ans(m+1, "");
    int it = 0;
    for(int i=1; i<=m; i++){
        long double r2 = 2.0L * q[i][0];
        while(it < edges.size() && std::get<0>(edges[it]) < r2){
            unite(std::get<1>(edges[it]), std::get<2>(edges[it]));
            it++;
        }
        int st = q[i][1];
        bool lr = (find_parent(find_parent, n + 2) == find_parent(find_parent, n + 4));
        bool tb = (find_parent(find_parent, n + 1) == find_parent(find_parent, n + 3));
        bool lb = (find_parent(find_parent, n + 1) == find_parent(find_parent, n + 4));
        bool br = (find_parent(find_parent, n + 1) == find_parent(find_parent, n + 2));
        bool rt = (find_parent(find_parent, n + 2) == find_parent(find_parent, n + 3));
        bool tl = (find_parent(find_parent, n + 3) == find_parent(find_parent, n + 4));
        for(int j=1; j<=4; j++){
            if(j == st){
                ans[q[i][2]] += std::to_string(j);
                continue;
            }
            bool can = true;
            if(st == 1){
                if(j == 2 && (lb || br || tb)) can = false;
                if(j == 3 && (lb || lr || tb || rt)) can = false;
                if(j == 4 && (lb || lr || tl)) can = false;
            }else if(st == 2){
                if(j == 1 && (lb || br || tb)) can = false;
                if(j == 3 && (lr || br || rt)) can = false;
                if(j == 4 && (lr || tl || br || tb)) can = false;
            }else if(st == 3){
                if(j == 1 && (lb || lr || tb || rt)) can = false;
                if(j == 2 && (lr || br || rt)) can = false;
                if(j == 4 && (tl || tb || rt)) can = false;
            }else if(st == 4){
                if(j == 1 && (lb || lr || tl)) can = false;
                if(j == 2 && (lr || tl || br || tb)) can = false;
                if(j == 3 && (tl || tb || rt)) can = false;
            }
            if(can) ans[q[i][2]] += std::to_string(j);
        }
    }
    for(int i=1; i<=m; i++) std::cout << ans[i] << '\n';
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...