oj.uz

Submission #378452

# Submission time Handle Problem Language Result Execution time Memory
378452 2021-03-16T20:07:44 Z Nima_Naderi Park (BOI16_park) C++14
100 / 100
 608 ms 72404 KB 
///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

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

# Verdict Execution time Memory Grader output
1 Correct 519 ms 66220 KB Output is correct
2 Correct 520 ms 66200 KB Output is correct
3 Correct 516 ms 66200 KB Output is correct
4 Correct 521 ms 66232 KB Output is correct
5 Correct 514 ms 66304 KB Output is correct
6 Correct 520 ms 66200 KB Output is correct
7 Correct 500 ms 66232 KB Output is correct
8 Correct 495 ms 66200 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 5352 KB Output is correct
2 Correct 86 ms 6248 KB Output is correct
3 Correct 85 ms 6248 KB Output is correct
4 Correct 85 ms 6248 KB Output is correct
5 Correct 86 ms 6248 KB Output is correct
6 Correct 89 ms 6248 KB Output is correct
7 Correct 82 ms 5600 KB Output is correct
8 Correct 82 ms 5720 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 66220 KB Output is correct
2 Correct 520 ms 66200 KB Output is correct
3 Correct 516 ms 66200 KB Output is correct
4 Correct 521 ms 66232 KB Output is correct
5 Correct 514 ms 66304 KB Output is correct
6 Correct 520 ms 66200 KB Output is correct
7 Correct 500 ms 66232 KB Output is correct
8 Correct 495 ms 66200 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 88 ms 5352 KB Output is correct
12 Correct 86 ms 6248 KB Output is correct
13 Correct 85 ms 6248 KB Output is correct
14 Correct 85 ms 6248 KB Output is correct
15 Correct 86 ms 6248 KB Output is correct
16 Correct 89 ms 6248 KB Output is correct
17 Correct 82 ms 5600 KB Output is correct
18 Correct 82 ms 5720 KB Output is correct
19 Correct 600 ms 72388 KB Output is correct
20 Correct 608 ms 72404 KB Output is correct
21 Correct 605 ms 72404 KB Output is correct
22 Correct 591 ms 72276 KB Output is correct
23 Correct 597 ms 72260 KB Output is correct
24 Correct 594 ms 72404 KB Output is correct