oj.uz

답안 #514133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
514133 2022-01-18T04:18:12 Z sberens Park (BOI16_park) C++17
100 / 100
 505 ms 71280 KB 
#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

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.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 439 ms 66132 KB Output is correct
2 Correct 423 ms 66024 KB Output is correct
3 Correct 430 ms 66144 KB Output is correct
4 Correct 432 ms 66120 KB Output is correct
5 Correct 430 ms 66156 KB Output is correct
6 Correct 429 ms 66232 KB Output is correct
7 Correct 419 ms 66152 KB Output is correct
8 Correct 407 ms 66168 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 7908 KB Output is correct
2 Correct 88 ms 9000 KB Output is correct
3 Correct 64 ms 8880 KB Output is correct
4 Correct 76 ms 9020 KB Output is correct
5 Correct 70 ms 8976 KB Output is correct
6 Correct 70 ms 9016 KB Output is correct
7 Correct 70 ms 8544 KB Output is correct
8 Correct 59 ms 8384 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 439 ms 66132 KB Output is correct
2 Correct 423 ms 66024 KB Output is correct
3 Correct 430 ms 66144 KB Output is correct
4 Correct 432 ms 66120 KB Output is correct
5 Correct 430 ms 66156 KB Output is correct
6 Correct 429 ms 66232 KB Output is correct
7 Correct 419 ms 66152 KB Output is correct
8 Correct 407 ms 66168 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 69 ms 7908 KB Output is correct
12 Correct 88 ms 9000 KB Output is correct
13 Correct 64 ms 8880 KB Output is correct
14 Correct 76 ms 9020 KB Output is correct
15 Correct 70 ms 8976 KB Output is correct
16 Correct 70 ms 9016 KB Output is correct
17 Correct 70 ms 8544 KB Output is correct
18 Correct 59 ms 8384 KB Output is correct
19 Correct 498 ms 71140 KB Output is correct
20 Correct 482 ms 71232 KB Output is correct
21 Correct 500 ms 71280 KB Output is correct
22 Correct 473 ms 71092 KB Output is correct
23 Correct 503 ms 71208 KB Output is correct
24 Correct 505 ms 71252 KB Output is correct