Submission #1104726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104726		thangdz2k7	Park (BOI16_park)	C++17	100 / 100	203 ms	27268 KiB

park

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int MaxN = 2e5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, m, w, h;

struct circle{
    int x, y, r;

    circle (){}

    circle (int _x, int _y, int _r) : x(_x), y(_y), r(_r) {}
};

ll sqr(int x){
    return ll(x) * x;
}

int dist(circle A, circle B){
    int d = sqrt(sqr(A.x - B.x) + sqr(A.y - B.y)) - A.r - B.r;
    return max(d, 0);
}

struct Edge{
    int u, v, w;

    bool operator < (Edge other){
        return w < other.w;
    }
};

struct DSU{
    vi par;

    DSU(int n){
        par.resize(n);
        for (int i = 0; i < n; ++ i) par[i] = i;
    }

    int find(int u){
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    bool check(int u, int v){
        return find(u) == find(v);
    }

    bool joint(int u, int v){
        u = find(u); v = find(v);
        if (u == v) return false;
        par[u] = v; return true;
    }
};

template <class Fun> class y_combinator_result { Fun fun_; public: template <class T> explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)) {} template <class...Args> decltype(auto)operator()(Args &&...args) { return fun_(ref(*this), forward<Args>(args)...); } };
template <class Fun> decltype(auto)y_combinator(Fun &&fun) { return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun)); }

template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
    static_assert(D >= 1, "Dimension must be positive");
    template <typename... Args>
    Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};

template <typename T>
struct Vec<1, T> : public vector<T> {
    Vec(int n = 0, T val = T()) : std::vector<T>(n, val) {}
};

void solve(){
    int n, m; cin >> n >> m;
    int w, h; cin >> w >> h;
    vector <circle> c(n);
    vector <Edge> e;
    int nvex = n + 4;
    for (int i = 0; i < n; ++ i){
        cin >> c[i].x >> c[i].y >> c[i].r;
        e.push_back({0, i + 4, c[i].y - c[i].r});
        e.push_back({2, i + 4, h - c[i].y - c[i].r});
        e.push_back({1, i + 4, w - c[i].x - c[i].r});
        e.push_back({3, i + 4, c[i].x - c[i].r});
    }

    for (int i = 0; i < n - 1; ++ i){
        for (int j = i + 1; j < n; ++ j)
            e.push_back({i + 4, j + 4, dist(c[i], c[j])});
    }

    sort(e.begin(), e.end());
    DSU T(nvex);
    vector <vector <ii>> adj(nvex);
    for (auto [u, v, w] : e){
        if (T.joint(u, v)){
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
    }

    auto dfs = y_combinator([&] (auto dfs, int u, int p, vector <int> &d) -> void{
        for (auto [v, w] : adj[u]) if (v ^ p){
            d[v] = max(d[u], w);
            dfs(v, u, d);
        }
    });

    vector <vi> d(4);
    for (int i = 0; i < 4; ++ i) {
        d[i].resize(nvex, 0);
        dfs(i, nvex, d[i]);
    }

    auto f = [&](int x, int y) -> pair <int, int> {
        return make_pair(min(x, y), max(x, y));
    };


    while (m --){
        int r, e; cin >> r >> e;
        r *= 2; -- e;
        if (d[e][(e + 4 - 1) % 4] < r){
            cout << e + 1 << endl;
            continue;
        }


        vector <int> ans = {e + 1};
        for (int o : {0, 1, 2, 3}) if (o ^ e){
            if (d[o][(o + 4 - 1) % 4] < r) continue;
            if (f(e, o) == ii(0, 3) || f(e, o) == ii(1, 2)){
                if (d[1][3] < r) continue;
            }
            if (f(e, o) == ii(0, 1) || f(e, o) == ii(2, 3)){
                if (d[0][2] < r) continue;
            }
            if (f(e, o) == ii(0, 2) || f(e, o) == ii(1, 3)){
                if (d[0][2] < r) continue;
                if (d[1][3] < r) continue;
            }
            ans.push_back(o + 1);
        }
        sort(ans.begin(), ans.end());
        for (int id : ans) cout << id;
        cout << endl;
    }
}

int main(){
    if (fopen("ESCAPING.inp", "r")){
        freopen("ESCAPING.inp", "r", stdin);
        freopen("ESCAPING.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message (stderr)

park.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
park.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
park.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
park.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
park.cpp: In function 'int main()':
park.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen("ESCAPING.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen("ESCAPING.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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