| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1097799 |
2024-10-08T09:39:57 Z |
pemguimn |
Park (BOI16_park) |
C++14 |
|
430 ms |
104856 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 10, M = 1e5 + 5;
int n, m, w, h, x[N], y[N], r[N], R[M], e[M], par[N], sz[N];
struct ev{
long double dist;
int t, x, y;
};
string res[M];
int root(int x){
if(x == par[x]) return x;
return par[x] = (root(par[x]));
}
void unite(int x, int y){
x = root(x), y = root(y);
if(x != y){
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
par[y] = x;
}
}
bool bound(int x, int y){
return (root(x) == root(y));
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> w >> h;
for(int i = 1; i <= n + 4; i++) par[i] = i, sz[i] = 1;
swap(w, h);
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i] >> r[i];
swap(x[i], y[i]);
}
vector<ev> events;
for(int i = 1; i <= n; i++){
events.push_back({1LL * x[i] - r[i], 1, i, n + 1});
events.push_back({1LL * (h - y[i]) - r[i], 1, i, n + 2});
events.push_back({1LL * (w - x[i]) - r[i], 1, i, n + 3});
events.push_back({1LL * y[i] - r[i], 1, i, n + 4});
}
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
long double dx = x[i] - x[j];
long double dy = y[i] - y[j];
events.push_back({sqrt(1LL * dx * dx + dy * dy) - r[i] - r[j], 1, i, j});
}
}
for(int i = 1; i <= m; i++){
cin >> R[i] >> e[i];
events.push_back({2LL * R[i], 0, i, 0});
}
sort(events.begin(), events.end(), [](ev x, ev y){
return x.dist < y.dist || (x.dist == y.dist && x.t < y.t);
});
for(ev cur : events){
if(cur.t == 1){
unite(cur.x, cur.y);
} else{
string ans = "";
bool go1 = true;
bool go2 = true;
bool go3 = true;
bool go4 = true;
if(e[cur.x] == 1){
if(bound(n + 1, n + 3)) go2 = go3 = false;
if(bound(n + 2, n + 4)) go4 = go3 = false;
if(bound(n + 1, n + 2)) go2 = false;
if(bound(n + 2, n + 3)) go3 = false;
if(bound(n + 3, n + 4)) go4 = false;
} else if(e[cur.x] == 2){
// vertical
if(bound(n + 1, n + 3)) go1 = go4 = false;
// horizontal
if(bound(n + 2, n + 4)) go4 = go3 = false;
if(bound(n + 1, n + 4)) go1 = false;
if(bound(n + 2, n + 3)) go3 = false;
if(bound(n + 3, n + 4)) go4 = false;
} else if(e[cur.x] == 3){
if(bound(n + 1, n + 3)) go1 = go4 = false;
if(bound(n + 2, n + 4)) go1 = go2 = false;
if(bound(n + 1, n + 4)) go1 = false;
if(bound(n + 1, n + 2)) go2 = false;
if(bound(n + 3, n + 4)) go4 = false;
} else{
if(bound(n + 1, n + 3)) go1 = go4 = false;
if(bound(n + 2, n + 4)) go1 = go2 = false;
if(bound(n + 1, n + 4)) go1 = false;
if(bound(n + 1, n + 2)) go2 = false;
if(bound(n + 2, n + 3)) go3 = false;
}
if(go1) ans += "1";
if(go2) ans += "2";
if(go3) ans += "3";
if(go4) ans += "4";
res[cur.x] = ans;
}
}
for(int i = 1; i <= m; i++) cout << res[i] << "\n";
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:45:38: warning: narrowing conversion of '((1 * x[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
45 | events.push_back({1LL * x[i] - r[i], 1, i, n + 1});
| ~~~~~~~~~~~^~~~~~
park.cpp:46:44: warning: narrowing conversion of '((1 * (h - y[i])) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
46 | events.push_back({1LL * (h - y[i]) - r[i], 1, i, n + 2});
| ~~~~~~~~~~~~~~~~~^~~~~~
park.cpp:47:44: warning: narrowing conversion of '((1 * (w - x[i])) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
47 | events.push_back({1LL * (w - x[i]) - r[i], 1, i, n + 3});
| ~~~~~~~~~~~~~~~~~^~~~~~
park.cpp:48:38: warning: narrowing conversion of '((1 * y[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
48 | events.push_back({1LL * y[i] - r[i], 1, i, n + 4});
| ~~~~~~~~~~~^~~~~~
park.cpp:59:31: warning: narrowing conversion of '(2 * R[i])' from 'long long int' to 'long double' [-Wnarrowing]
59 | events.push_back({2LL * R[i], 0, i, 0});
| ~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
425 ms |
104616 KB |
Output is correct |
| 2 |
Correct |
430 ms |
104852 KB |
Output is correct |
| 3 |
Correct |
407 ms |
104348 KB |
Output is correct |
| 4 |
Correct |
408 ms |
103344 KB |
Output is correct |
| 5 |
Correct |
402 ms |
103356 KB |
Output is correct |
| 6 |
Correct |
404 ms |
103212 KB |
Output is correct |
| 7 |
Correct |
398 ms |
103332 KB |
Output is correct |
| 8 |
Correct |
409 ms |
104856 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
11208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
425 ms |
104616 KB |
Output is correct |
| 2 |
Correct |
430 ms |
104852 KB |
Output is correct |
| 3 |
Correct |
407 ms |
104348 KB |
Output is correct |
| 4 |
Correct |
408 ms |
103344 KB |
Output is correct |
| 5 |
Correct |
402 ms |
103356 KB |
Output is correct |
| 6 |
Correct |
404 ms |
103212 KB |
Output is correct |
| 7 |
Correct |
398 ms |
103332 KB |
Output is correct |
| 8 |
Correct |
409 ms |
104856 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 11 |
Incorrect |
42 ms |
11208 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
