# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
378452 |
2021-03-16T20:07:44 Z |
Nima_Naderi |
Park (BOI16_park) |
C++14 |
|
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));
| ~~~~~~~~~^
# |
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 |
# |
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 |
# |
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 |