Submission #1352443

#TimeUsernameProblemLanguageResultExecution timeMemory
1352443jadai007Park (BOI16_park)C++20
0 / 100
322 ms66192 KiB
#include <bits/stdc++.h>
#define ld long double

using namespace std;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, w, h; cin >> n >> m >> w >> h;
    vector<array<int, 3>> a(n + 1);
    for(int i = 1; i <= n; ++i) cin >> a[i][0] >> a[i][1] >> a[i][2];
    vector<array<int, 3>> q(m + 1);
    for(int i = 1; i <= m; ++i){
        cin >> q[i][0] >> q[i][1];
        q[i][2] = i;
    }
    sort(q.begin() + 1, q.end());
    vector<tuple<ld, int, int>> edges;
    for(int i = 1; i <= n; ++i){
        edges.emplace_back((ld)(a[i][1] - a[i][2]), i, n + 1);
        edges.emplace_back((ld)(w - a[i][0] - a[i][2]), i, n + 2);
        edges.emplace_back((ld)(h - a[i][1] - a[i][2]), i, n + 3);
        edges.emplace_back((ld)(a[i][0] - a[i][2]), i, n + 4);
        for(int j = i + 1; j <= n; ++j){
            long long dx = a[i][0] - a[j][0];
            long long dy = a[i][1] - a[j][1];
            ld dist = sqrt(dx * dx + dy * dy);
            edges.emplace_back(dist - (ld)(a[i][2] - a[j][2]), i, j);
        }
    }
    sort(edges.begin(), edges.end());
    vector<int> pa(n + 10);
    iota(pa.begin() + 1, pa.end(), 1);
    auto fp = [&](auto &&fp, int u) -> int {
        if(pa[u] == u) return u;
        return pa[u] = fp(fp, pa[u]);
    };
    auto unite = [&](int u, int v) -> void {
        int ru = fp(fp, u), rv = fp(fp, v);
        if(ru != rv) pa[ru] = rv;
    };
    vector<string> ans(m + 1, "");
    int it = 0;
    for(int i = 1; i <= m; ++i){
        ld r2 = 2.0L * q[i][0];
        while(it < edges.size() && get<0>(edges[it]) < r2){
            unite(get<1>(edges[it]), get<2>(edges[it]));
            ++it;
        }
        int st = q[i][1];
        bool lr = (fp(fp, n + 4) == fp(fp, n + 2)), tb = (fp(fp, n + 3) == fp(fp, n + 1)), lb = (fp(fp, n + 4) == fp(fp, n + 1)); 
        bool br = (fp(fp, n + 1) == fp(fp, n + 2)), rt = (fp(fp, n + 2) == fp(fp, n + 3)), tl = (fp(fp, n + 3) == fp(fp, n + 4)); 
        for(int j = 1; j <= 4; ++j){
            if(j == st){
                ans[q[i][2]] += char('0' + 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]] += char('0' + j);
        }
    }
    for(int i = 1; i <= m; ++i) cout << ans[i] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...