oj.uz

답안 #525169

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525169 2022-02-11T01:55:38 Z vijay Park (BOI16_park) C++17
100 / 100
 521 ms 70236 KB 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <array>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>


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>
const ll M = 1000000007;

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);
		// ifstream cin;
		// cin.open("test.in");

    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:153: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]
  153 |         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:123:29:   required from here
park.cpp:44:42: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   44 | #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
      |                                          ^
park.cpp:45:19: note: in expansion of macro 'FOR'
   45 | #define F0R(i, a) FOR(i,0,a)
      |                   ^~~
park.cpp:51:5: note: in expansion of macro 'F0R'
   51 |     F0R(i, N) in >> arr[i];
      |     ^~~

Subtask #1
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 419 ms 66024 KB Output is correct
2 Correct 423 ms 66092 KB Output is correct
3 Correct 424 ms 66112 KB Output is correct
4 Correct 417 ms 66040 KB Output is correct
5 Correct 439 ms 66092 KB Output is correct
6 Correct 461 ms 66240 KB Output is correct
7 Correct 416 ms 66024 KB Output is correct
8 Correct 405 ms 66136 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 77 ms 7900 KB Output is correct
2 Correct 68 ms 7904 KB Output is correct
3 Correct 67 ms 7896 KB Output is correct
4 Correct 66 ms 7880 KB Output is correct
5 Correct 69 ms 7868 KB Output is correct
6 Correct 93 ms 7912 KB Output is correct
7 Correct 64 ms 7164 KB Output is correct
8 Correct 60 ms 7176 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 419 ms 66024 KB Output is correct
2 Correct 423 ms 66092 KB Output is correct
3 Correct 424 ms 66112 KB Output is correct
4 Correct 417 ms 66040 KB Output is correct
5 Correct 439 ms 66092 KB Output is correct
6 Correct 461 ms 66240 KB Output is correct
7 Correct 416 ms 66024 KB Output is correct
8 Correct 405 ms 66136 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 77 ms 7900 KB Output is correct
12 Correct 68 ms 7904 KB Output is correct
13 Correct 67 ms 7896 KB Output is correct
14 Correct 66 ms 7880 KB Output is correct
15 Correct 69 ms 7868 KB Output is correct
16 Correct 93 ms 7912 KB Output is correct
17 Correct 64 ms 7164 KB Output is correct
18 Correct 60 ms 7176 KB Output is correct
19 Correct 506 ms 70184 KB Output is correct
20 Correct 480 ms 70128 KB Output is correct
21 Correct 504 ms 70236 KB Output is correct
22 Correct 521 ms 70112 KB Output is correct
23 Correct 489 ms 70116 KB Output is correct
24 Correct 472 ms 70220 KB Output is correct