Submission #378452

#	Time	Username	Problem	Language	Result	Execution time	Memory
378452		Nima_Naderi	Park (BOI16_park)	C++14	100 / 100	608 ms	72404 KiB

park

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
const ll MXN = 2e3 + 10;
const ll MXQ = 1e5 + 10;
ll n, q, w, h, up, dn, rt, lt, pnt;
ll Par[MXN], Sz[MXN];
ll Ox[MXN], Oy[MXN], R[MXN];
vector<pair<ld, pair<ll, ll>>> E, Q;
bool ANS[MXQ][4];
ll Find(ll u){
    return (Par[u] == u ? u : Par[u] = Find(Par[u]));
}
void Union(ll u, ll v){
    u = Find(u), v = Find(v);
    if(u == v) return;
    if(Sz[u] < Sz[v]) swap(u, v);
    Sz[u] += Sz[v], Par[v] = u;
}
ld dis(ll i, ll j){
    ll dx = Ox[i] - Ox[j], dy = Oy[i] - Oy[j];
    dx *= dx, dy *= dy;
    ld d = sqrtl(dx + dy) - R[i] - R[j];
    return d;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    iota(Par, Par + MXN, 0), fill(Sz, Sz + MXN, 1);
    cin >> n >> q >> w >> h;
    up = ++ n, rt = ++ n, dn = ++ n, lt = ++ n;
    for(int i = 1; i <= n - 4; i ++){
        cin >> Ox[i] >> Oy[i] >> R[i];
        E.push_back({Oy[i] - R[i], {up, i}});
        E.push_back({w - Ox[i] - R[i], {rt, i}});
        E.push_back({h - Oy[i] - R[i], {dn, i}});
        E.push_back({Ox[i] - R[i], {lt, i}});
        for(int j = 1; j < i; j ++){
            E.push_back({dis(i, j), {i, j}});
        }
    }
    for(int i = 1; i <= q; i ++){
        ld r; ll typ; cin >> r >> typ;
        Q.push_back({r * 2.0, {typ, i}});
    }
    sort(E.begin(), E.end()), sort(Q.begin(), Q.end());
    for(auto X : Q){
        ld mx = X.first; ll typ, id; tie(typ, id) = X.second;
        while(pnt < E.size() && E[pnt].first < mx){
            ll u, v; tie(u, v) = E[pnt].second;
            Union(u, v), pnt ++;
        }
        ANS[id][typ] = 1;
        if(typ == 1){
            ANS[id][2] = (Find(up) != Find(rt) && Find(up) != Find(dn) && Find(up) != Find(lt));
            ANS[id][3] = (Find(up) != Find(lt) && Find(up) != Find(dn) && Find(rt) != Find(lt) && Find(rt) != Find(dn));
            ANS[id][4] = (Find(lt) != Find(up) && Find(lt) != Find(rt) && Find(lt) != Find(dn));
        } else
        if(typ == 2){
            ANS[id][1] = (Find(up) != Find(rt) && Find(up) != Find(dn) && Find(up) != Find(lt));
            ANS[id][3] = (Find(rt) != Find(up) && Find(rt) != Find(dn) && Find(rt) != Find(lt));
            ANS[id][4] = (Find(up) != Find(rt) && Find(up) != Find(dn) && Find(rt) != Find(lt) && Find(dn) != Find(lt));
        } else
        if(typ == 3){
            ANS[id][1] = (Find(up) != Find(lt) && Find(up) != Find(dn) && Find(rt) != Find(lt) && Find(rt) != Find(dn));
            ANS[id][2] = (Find(rt) != Find(up) && Find(rt) != Find(dn) && Find(rt) != Find(lt));
            ANS[id][4] = (Find(dn) != Find(up) && Find(dn) != Find(rt) && Find(dn) != Find(lt)) ;
        } else {
            ANS[id][1] = (Find(lt) != Find(up) && Find(lt) != Find(rt) && Find(lt) != Find(dn));
            ANS[id][2] = (Find(up) != Find(rt) && Find(up) != Find(dn) && Find(rt) != Find(lt) && Find(dn) != Find(lt));
            ANS[id][3] = (Find(dn) != Find(up) && Find(dn) != Find(rt) && Find(dn) != Find(lt));
        }
    }
    for(int i = 1; i <= q; i ++){
        for(int j = 1; j <= 4; j ++) if(ANS[i][j]){
            cout << j;
        } cout << '\n';
    }
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:52:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         while(pnt < E.size() && E[pnt].first < mx){
      |               ~~~~^~~~~~~~~~
park.cpp:78:49: warning: iteration 3 invokes undefined behavior [-Waggressive-loop-optimizations]
   78 |         for(int j = 1; j <= 4; j ++) if(ANS[i][j]){
      |                                         ~~~~~~~~^
park.cpp:78:26: note: within this loop
   78 |         for(int j = 1; j <= 4; j ++) if(ANS[i][j]){
      |                        ~~^~~~
park.cpp:70:22: warning: array subscript 4 is above array bounds of 'bool [4]' [-Warray-bounds]
   70 |             ANS[id][4] = (Find(dn) != Find(up) && Find(dn) != Find(rt) && Find(dn) != Find(lt)) ;
      |             ~~~~~~~~~^
park.cpp:65:22: warning: array subscript 4 is above array bounds of 'bool [4]' [-Warray-bounds]
   65 |             ANS[id][4] = (Find(up) != Find(rt) && Find(up) != Find(dn) && Find(rt) != Find(lt) && Find(dn) != Find(lt));
      |             ~~~~~~~~~^
park.cpp:60:22: warning: array subscript 4 is above array bounds of 'bool [4]' [-Warray-bounds]
   60 |             ANS[id][4] = (Find(lt) != Find(up) && Find(lt) != Find(rt) && Find(lt) != Find(dn));
      |             ~~~~~~~~~^

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