제출 #321408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
321408		Falcon	Park (BOI16_park)	C++17	27 / 100	571 ms	94444 KiB

park

#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[w]].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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42