Submission #534508

#	Time	Username	Problem	Language	Result	Execution time	Memory
534508		huB1erTi2	Park (BOI16_park)	C++17	100 / 100	1460 ms	1788 KiB

park

//   _|                                                _|
//   _|  _|    _|    _|    _|_|    _|_|_|      _|_|_|  _|  _|      _|_|      _|_|
//   _|_|      _|    _|  _|_|_|_|  _|    _|  _|_|      _|_|      _|_|_|_|  _|_|_|_|
//   _|  _|    _|    _|  _|        _|    _|      _|_|  _|  _|    _|        _|
//   _|    _|    _|_|_|    _|_|_|  _|_|_|    _|_|_|    _|    _|    _|_|_|    _|_|_|
//                   _|            _|
//               _|_|              _|
#include <iostream>
#include <numeric>
#include <cmath>
#include <vector>

using namespace std;

// #define DEBUG
#ifdef DEBUG
#define dassert(x) assert(x);
#define df(...) printf(__VA_ARGS__)
#else
#define dassert(x)
#define df(...)
#endif

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define ir(x, a, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define sz(x) (ll)x.size()
#define foru(i, n) for (int i = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()

typedef int64_t ll;

int read() {
    int n = 0; bool b = 0; char c = getchar();
    for (; !ir(c, '0', '9'); c = getchar()) b = (c == '-');
    for (; ir(c, '0', '9'); c = getchar()) n = 10*n + (c-'0');
    if (b) return -n;
    return n;
}

struct circle {
    ll x, y, r;
};

struct dsu {
    int n;
    vec<int> over, rank;
    dsu(int n) : n(n), over(n), rank(n) {
        iota(all(over), 0);
    }
    
    int find(int x) {
        if (over[x] == x) return x;
        return over[x] = find(over[x]);
    }
    
    void unify(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return;
        if (rank[x] < rank[y]) swap(x, y);
        over[y] = x;
        if (rank[x] == rank[y]) ++rank[x];
    }
};

ll ss(ll x) {
    return x*x;
}

bool canplace(const vec<circle>& cs, circle c) {
    for (auto cc : cs) {
        if (ss(cc.x-c.x) + ss(cc.y-c.y) < ss(cc.r + c.r)) return 0;
    }
    return 1;
}

bool check(vec<circle> cs, ll fit, int from, int to, ll w, ll h) {
    int n = cs.size();
    dsu d(n+4);
    for (int i = 0; i < n; ++i) {
        ll x = cs[i].x, y = cs[i].y, r = cs[i].r;
        if (x < fit + r) d.unify(i, n);
        if (w-x < fit + r) d.unify(i, n+1);
        if (y < fit + r) d.unify(i, n+2);
        if (h-y < fit + r) d.unify(i, n+3);
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            ll width = fit + cs[i].r + cs[j].r;
            ll d2 = ss(cs[i].x - cs[j].x) + ss(cs[i].y - cs[j].y);
            if (d2 < ss(width)) {
                d.unify(i, j);
            }
        }
    }
    
    if (to < from) swap(to, from);
    --to, --from;
    //               1    2    3    4
    vec<int> cool = {n+2, n+1, n+3, n};
    vec<int> sidea, sideb;
    for (int i = 0; i < 4; ++i) {
        if (from <= i && i < to) sidea.pb(cool[i]);
        else sideb.pb(cool[i]);
    }
    // for (auto a : sidea) {
    //     cout << a << " ";
    // }
    // cout << "\n";
    // for (auto b : sideb) {
    //     cout << b << " ";
    // }
    // cout << "\n";
    // for (int i = 0; i < 4; ++i) {
    //     for (int j = 0; j < 4; ++j) {
    //         cout << ((d.find(n+i) == d.find(n+j)) ? '1' : '0') << ' ';
    //     }
    //     cout << "\n";
    // }
    for (auto a : sidea) {
        for (auto b : sideb) {
            if (d.find(a) == d.find(b)) return 0;
        }
    }
    // cout << "\n";
    return 1;
}

ll search(const vec<circle>& cs, int from, int to, ll w, ll h) {
    ll lo = 1, hi = min(w,h)/2+10;
    while (lo+1 < hi) {
        ll mid = (lo+hi)/2;
        if (check(cs, 2*mid, from, to, w, h)) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int main() {
    df("debug mode\n");
#ifndef DEBUG
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
    int n, m;
    ll w, h;
    cin >> n >> m >> w >> h;
    vec<circle> cs(n);
    foru (i, n) {
        ll x, y, r;
        cin >> x >> y >> r;
        cs[i] = {x, y, r};
    }
    int best[5][5];
    for (int i = 1; i <= 4; ++i) {
        for (int j = i+1; j <= 4; ++j) {
            best[i][j] = best[j][i] = search(cs, i, j, w, h);
        }
    }
    // for (int i = 1; i <= 4; ++i) {
    //     for (int j = 1; j <= 4; ++j) {
    //         cout << best[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    foru (i, m) {
        int no, r;
        cin >> r >> no;
        // cout << no << " " << r << endl;
        for (int i = 1; i <= 4; ++i) {
            if (i == no || r <= best[no][i]) {
                cout << i;
            }
        }
        cout << "\n";
    }
    return 0;
}

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