Submission #514133

#	Time	Username	Problem	Language	Result	Execution time	Memory
514133		sberens	Park (BOI16_park)	C++17	100 / 100	505 ms	71280 KiB

park

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)

template<typename T, unsigned long N>
istream & operator>>(istream& in, array<T, N>& arr) {
    F0R(i, N) in >> arr[i];
    return in;
}

using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

template<typename T>
using oset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

const ll M = 1000000007;
const ll infll = M * M;

struct dsu {

    vector<int> p, sz;

    explicit dsu(int n) : p(n), sz(n, 1) {
        iota(p.begin(), p.end(), 0);
    }

    int rep(int x) {
        while (x != p[x]) x = p[x] = p[p[x]];
        return x;
    }

    // returns true if a and b are in the same set, and then unites them.
    bool unite(int a, int b) {
        a = rep(a), b = rep(b);
        if (sz[a] < sz[b]) swap(a, b);
        if (a != b) {
            p[b] = a;
            sz[a] += sz[b];
        }
        return a == b;
    }

    // returns true if a and b are in the same set.
    bool query(int a, int b) {
        return rep(a) == rep(b);
    }

    // returns the size of the set containing x
    int size(int x) {
        return sz[rep(x)];
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, w, h;
    cin >> n >> m >> w >> h;
    vector<array<int, 3>> trees(n);
    F0R(i, n) cin >> trees[i];
    vector<array<int, 3>> visitors(m);
    F0R(i, m) {
        cin >> visitors[i][0] >> visitors[i][1];
        visitors[i][2] = i;
    }
    vector<tuple<ld, int, int>> edges;
    const int L = n, T = n+1, R = n+2, B = n+3;
    F0R(i, n) {
        auto[x1, y1, r1] = trees[i];
        FOR(j, i+1, n){
            auto[x2, y2, r2] = trees[j];
            edges.eb(sqrt(pow((ld)x1-x2,2) + pow((ld)y1-y2,2)) -r1 -r2, i, j);
        }
        edges.eb(x1-r1, L, i);
        edges.eb(y1-r1, T, i);
        edges.eb(w-(x1+r1), R, i);
        edges.eb(h-(y1+r1), B, i);
    }
    sort(all(edges));
    sort(all(visitors));
    int ce = 0;
    dsu d(n+4);
    set<int> disc;
    auto has_any = [&](vi v) -> bool {
        for (int x : v) if (disc.count(x) == 1) return true;
        return false;
    };
    vvi res(m);
    for (auto [r, e, resi] : visitors) {
        while (ce < edges.size() && get<0>(edges[ce]) < 2 * r) {
            d.unite(get<1>(edges[ce]), get<2>(edges[ce]));
            ++ce;
        }
        if (d.query(L, T)) disc.insert(0);
        if (d.query(T, R)) disc.insert(1);
        if (d.query(R, B)) disc.insert(2);
        if (d.query(B, L)) disc.insert(3);
        if (d.query(L, R)) disc.insert(4);
        if (d.query(T, B)) disc.insert(5);
        if (e == 1) {
            res[resi].pb(1);
            if (!has_any({0,1,5})) res[resi].pb(2);
            if (!has_any({0,2,4,5})) res[resi].pb(3);
            if (!has_any({0, 4, 3})) res[resi].pb(4);
        } else if (e == 4) {
            if (!has_any({0,3,4})) res[resi].pb(1);
            if (!has_any({4,5,1,3})) res[resi].pb(2);
            if (!has_any({3,2,5})) res[resi].pb(3);
            res[resi].pb(4);
        } else if (e == 3) {
            if (!has_any({0,2,4,5})) res[resi].pb(1);
            if (!has_any({2,1,4})) res[resi].pb(2);
            res[resi].pb(3);
            if (!has_any({2,3,5})) res[resi].pb(4);
        }else if (e == 2) {
            if (!has_any({0,1,5})) res[resi].pb(1);
            res[resi].pb(2);
            if (!has_any({1,2,4})) res[resi].pb(3);
            if (!has_any({4,5,1,3})) res[resi].pb(4);
        }
    }
    F0R(i, m) {
        for (int x : res[i]) cout << x;
        cout << '\n';
    }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:127:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long double, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         while (ce < edges.size() && get<0>(edges[ce]) < 2 * r) {
      |                ~~~^~~~~~~~~~~~~~
park.cpp: In instantiation of 'std::istream& operator>>(std::istream&, std::array<_Tp, _Nm>&) [with T = int; long unsigned int N = 3; std::istream = std::basic_istream<char>]':
park.cpp:97:29:   required from here
park.cpp:18:42: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   18 | #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
      |                                          ^
park.cpp:19:19: note: in expansion of macro 'FOR'
   19 | #define F0R(i, a) FOR(i,0,a)
      |                   ^~~
park.cpp:25:5: note: in expansion of macro 'F0R'
   25 |     F0R(i, N) in >> arr[i];
      |     ^~~

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