oj.uz

Submission #321417

# Submission time Handle Problem Language Result Execution time Memory
321417 2020-11-12T09:46:27 Z Falcon Park (BOI16_park) C++17
100 / 100
 651 ms 94528 KB 
#pragma GCC optimize("O2")

#include <bits/stdc++.h>

#ifdef DEBUG
#include "debug.hpp"
#endif

using namespace std;

#define all(c)              (c).begin(), (c).end()
#define rall(c)             (c).rbegin(), (c).rend()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rrep(i, N)          for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d)    for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
#define debug(x...)         { ++dbg::depth; string dbg_vals = dbg::to_string(x); --dbg::depth; dbg::fprint(__func__, __LINE__, #x, dbg_vals); }
#define light_debug(x)      { dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0; }
#else
#define debug(x...)         42
#define light_debug(x)      42
#endif


template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

class disjoint_set_union {
    int n;
    mutable vector<int> p;

private:

    int root(int i) const {
        return ~p[i] ? p[i] = root(p[i]) : i;
    }

public:

    disjoint_set_union(int n_) : n{n_}, p(n, -1) {};

    void merge(int i, int j) {
        i = root(i), j = root(j);
        if(i != j) p[i] = j;
    }

    bool joined(int i, int j) const {
        return root(i) == root(j);
    }
};

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

#ifdef DEBUG
    freopen("debug", "w", stderr);
#endif

    int n, m, w, h; cin >> n >> m >> w >> h;
    const int TOP = n, BTM = n + 1, LFT = n + 2, RGT = n + 3;

    struct tree {
        ll x, y, r;
    };
    vector<tree> trees(n);
    for(auto& t : trees) cin >> t.x >> t.y >> t.r;

    auto max_r = [](const tree& i, const tree& j) -> ll {
        ll s = i.r + j.r;
        ll dx = i.x - j.x, dy = i.y - j.y;
        ll d = dx * dx + dy * dy;
        if(s * s > d) return -1;
        
        // We need (2r + i.r + j.r) ^ 2 <= d
        ll r = 0;
        for(ll k = 1LL << 28; k; k >>= 1) {
            ll tmp = (r + k) * 2 + s;
            if(tmp * tmp <= d) r += k;
        } 

        return r;
    };

    vector<array<ll, 3>> tree_pairs; tree_pairs.reserve(n * (n - 1) / 2);
    rep(i, n)
        rep2(j, i + 1, n - 1)
            tree_pairs.pb({max_r(trees[i], trees[j]), i, j});
    rep(i, n) {
        auto t = trees[i]; debug(t.x, t.y, t.r);
        tree_pairs.pb({(t.x - t.r) / 2, i, LFT});
        tree_pairs.pb({(t.y  - t.r) / 2, i, BTM});
        tree_pairs.pb({(w - t.x - t.r) / 2, i, RGT});
        tree_pairs.pb({(h - t.y - t.r) / 2, i, TOP});
    }
    sort(all(tree_pairs));

    debug(tree_pairs);

    vector<array<int, 3>> queries(m); // {r, e, i}
    rep(i, m) cin >> queries[i][0] >> queries[i][1], queries[i][2] = i;
    sort(all(queries));

    disjoint_set_union dsu(n + 4);
    vector<string> ans(m);
    auto tp = tree_pairs.begin();
    for(const auto& q : queries) {
        while(tp != tree_pairs.end()) {
            auto p = *tp;
            if(p[0] < q[0])
                dsu.merge(p[1], p[2]);
            else
                break;
            ++tp;
        }

        switch(q[1]) {
            case 1: // Bottom Left
                ans[q[2]].pb('1');
                if(!dsu.joined(BTM, TOP) 
                        && !dsu.joined(BTM, LFT) 
                        && !dsu.joined(BTM, RGT))
                    ans[q[2]].pb('2');
                if(!dsu.joined(BTM, TOP) 
                        && !dsu.joined(BTM, LFT) 
                        && !dsu.joined(TOP, RGT) 
                        && !dsu.joined(LFT, RGT))
                    ans[q[2]].pb('3');
                if(!dsu.joined(BTM, LFT)
                        && !dsu.joined(LFT, RGT)
                        && !dsu.joined(TOP, LFT))
                    ans[q[2]].pb('4');
                break;

            case 2: // Bottom right
                if(!dsu.joined(BTM, TOP) 
                        && !dsu.joined(BTM, LFT) 
                        && !dsu.joined(BTM, RGT))
                    ans[q[2]].pb('1');
                ans[q[2]].pb('2');
                if(!dsu.joined(BTM, RGT)
                        && !dsu.joined(TOP, RGT)
                        && !dsu.joined(LFT, RGT))
                    ans[q[2]].pb('3');
                if(!dsu.joined(BTM, RGT)
                        && !dsu.joined(LFT, RGT)
                        && !dsu.joined(TOP, BTM)
                        && !dsu.joined(LFT, TOP))
                    ans[q[2]].pb('4');
                break;

            case 3: // Top right
                if(!dsu.joined(BTM, TOP) 
                        && !dsu.joined(BTM, LFT) 
                        && !dsu.joined(TOP, RGT) 
                        && !dsu.joined(LFT, RGT))
                    ans[q[2]].pb('1');
                if(!dsu.joined(BTM, RGT)
                        && !dsu.joined(TOP, RGT)
                        && !dsu.joined(LFT, RGT))
                    ans[q[2]].pb('2');
                ans[q[2]].pb('3');
                if(!dsu.joined(BTM, TOP)
                        && !dsu.joined(TOP, LFT)
                        && !dsu.joined(TOP, RGT))
                    ans[q[2]].pb('4');
                break;

            case 4: // Top left
                if(!dsu.joined(BTM, LFT)
                        && !dsu.joined(LFT, RGT)
                        && !dsu.joined(TOP, LFT))
                    ans[q[2]].pb('1');
                if(!dsu.joined(BTM, RGT)
                        && !dsu.joined(LFT, RGT)
                        && !dsu.joined(TOP, BTM)
                        && !dsu.joined(LFT, TOP))
                    ans[q[2]].pb('2');
                if(!dsu.joined(BTM, TOP)
                        && !dsu.joined(TOP, LFT)
                        && !dsu.joined(TOP, RGT))
                    ans[q[2]].pb('3');
                ans[q[2]].pb('4');
                break;
        }

        debug(q, ans[q[2]]);
    }

    for(auto& s : ans) cout << s << '\n';


#ifdef DEBUG
    dbg::dout << "\nExecution time: " << clock() << "ms\n";
#endif
    return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:26:29: warning: statement has no effect [-Wunused-value]
   26 | #define debug(x...)         42
      |                             ^~
park.cpp:104:28: note: in expansion of macro 'debug'
  104 |         auto t = trees[i]; debug(t.x, t.y, t.r);
      |                            ^~~~~
park.cpp:26:29: warning: statement has no effect [-Wunused-value]
   26 | #define debug(x...)         42
      |                             ^~
park.cpp:112:5: note: in expansion of macro 'debug'
  112 |     debug(tree_pairs);
      |     ^~~~~
park.cpp:26:29: warning: statement has no effect [-Wunused-value]
   26 | #define debug(x...)         42
      |                             ^~
park.cpp:201:9: note: in expansion of macro 'debug'
  201 |         debug(q, ans[q[2]]);
      |         ^~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 94464 KB Output is correct
2 Correct 511 ms 94444 KB Output is correct
3 Correct 505 ms 94444 KB Output is correct
4 Correct 522 ms 94316 KB Output is correct
5 Correct 518 ms 94444 KB Output is correct
6 Correct 508 ms 94316 KB Output is correct
7 Correct 493 ms 94316 KB Output is correct
8 Correct 485 ms 94316 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6552 KB Output is correct
2 Correct 70 ms 6592 KB Output is correct
3 Correct 65 ms 6540 KB Output is correct
4 Correct 70 ms 6540 KB Output is correct
5 Correct 69 ms 6552 KB Output is correct
6 Correct 63 ms 6552 KB Output is correct
7 Correct 61 ms 6124 KB Output is correct
8 Correct 60 ms 6148 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 94464 KB Output is correct
2 Correct 511 ms 94444 KB Output is correct
3 Correct 505 ms 94444 KB Output is correct
4 Correct 522 ms 94316 KB Output is correct
5 Correct 518 ms 94444 KB Output is correct
6 Correct 508 ms 94316 KB Output is correct
7 Correct 493 ms 94316 KB Output is correct
8 Correct 485 ms 94316 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 67 ms 6552 KB Output is correct
12 Correct 70 ms 6592 KB Output is correct
13 Correct 65 ms 6540 KB Output is correct
14 Correct 70 ms 6540 KB Output is correct
15 Correct 69 ms 6552 KB Output is correct
16 Correct 63 ms 6552 KB Output is correct
17 Correct 61 ms 6124 KB Output is correct
18 Correct 60 ms 6148 KB Output is correct
19 Correct 608 ms 94444 KB Output is correct
20 Correct 651 ms 94528 KB Output is correct
21 Correct 565 ms 94444 KB Output is correct
22 Correct 559 ms 94444 KB Output is correct
23 Correct 560 ms 94444 KB Output is correct
24 Correct 561 ms 94444 KB Output is correct