| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 944648 |
2024-03-13T02:33:25 Z |
thefless |
Park (BOI16_park) |
C++14 |
|
1286 ms |
3164 KB |
#include<bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define Times (1.0 * clock() / CLOCKS_PER_SEC)
#define fi first
#define base 31
#define sz(x) (int)(x).size()
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
#define task "name"
#define tsk ""
const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int MOD2 = 1e9 + 696969;
const int N = 2e5 + 3;
const int BASE = 10;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
struct DSU{
vector<int> par;
DSU(int n = 0): par(n + 7 , -1) {}
int get(int v){return par[v] < 0 ? v : par[v] = get(par[v]);}
bool same_set(int a , int b){return get(a) == get(b);}
bool unite(int a , int b){
a = get(a); b = get(b);
if(a == b) return 0;
par[a] += par[b];
par[b] = a;
return 1;
}
}dsu;
int n , m , w , h;
int square[5];
int cango[5][5];
vector<pii> need_check[5][5];
struct point
{
int x , y , r;
point(int x = 0 , int y = 0 , int r = 0): x{x} , y{y} , r{r} {}
}tree[N];
ll sqr(ll x){return x * x;}
double dist(point u , point v){
double f = u.r + v.r;
return sqrt(sqr(u.x - v.x) + sqr(u.y - v.y)) - f;
}
ll dist1(point u , point v){
int f = u.r + v.r;
return max(0.0 , sqrt(sqr(u.x - v.x) + sqr(u.y - v.y)) - f);
}
bool check(int x , int num){
for(int i = 1 ; i <= n ; i++){
if(num == 1){
if(dist(point(w - x , x , x) , tree[i]) < 0) return 0;
}
if(num == 2){
if(dist(point(w - x , h - x , x) , tree[i]) < 0) return 0;
}
if(num == 3){
if(dist(point(x , h - x , x) , tree[i]) < 0) return 0;
}
if(num == 4){
if(dist(point(x , x , x) , tree[i]) < 0) return 0;
}
}
return 1;
}
int cnp1(int l , int r , int num){
while(1){
if(l == r) return l;
if(r - l == 1){
if(check(r , num)) return r;
return l;
}
int mid = l + r >> 1;
if(check(mid , num)) l = mid;
else r = mid;
}
}
bool kt(int x , int c , int d){
dsu = DSU(n);
for(int i = 1 ; i <= n ; i++){
if(tree[i].x - tree[i].r < x) dsu.unite(i , n + 1);
if(tree[i].y - tree[i].r < x) dsu.unite(i , n + 2);
if(w - (tree[i].x + tree[i].r) < x) dsu.unite(i , n + 3);
if(h - (tree[i].y + tree[i].r) < x) dsu.unite(i , n + 4);
}
for(int i = 2 ; i <= n ; i++){
for(int j = 1 ; j < i ; j++){
if(dist(tree[i] , tree[j]) < x) dsu.unite(i , j);
}
}
for(auto x : need_check[min(c , d)][max(c , d)]){
if(dsu.same_set(n + x.fi , n + x.se)) return 0;
}
return 1;
}
int cnp2(int l , int r , int c , int d){
while(1){
if(l == r) return l;
if(r - l == 1){
if(kt(2 * r , c , d)) return r;
return l;
}
int mid = l + r >> 1;
if(kt(2 * mid , c , d)) l = mid;
else r = mid;
}
}
void Solve(){
cin >> n >> m;
cin >> w >> h;
for(int i = 1 ; i <= n ; i++){
cin >> tree[i].x >> tree[i].y >> tree[i].r;
}
for(int i = 1 ; i <= 4 ; i++){
square[i] = cnp1(0 , min(w , h) , i);
}
need_check[1][2] = vector<pii>({{1 , 4} , {2 , 4} , {3 , 4}});
need_check[1][3] = vector<pii>({{1 , 3} , {2 , 4} , {2 , 3} , {1 , 4}});
need_check[1][4] = vector<pii>({{1 , 2} , {1 , 3} , {1 , 4}});
need_check[2][3] = vector<pii>({{3 , 1} , {3 , 2} , {3 , 4}});
need_check[2][4] = vector<pii>({{1 , 3} , {2 , 4} , {1 , 2} , {3 , 4}});
need_check[3][4] = vector<pii>({{2 , 4} , {1 , 2} , {3 , 2}});
for(int i = 1 ; i <= 4 ; i++){
for(int j = 1 ; j < i ; j++){
cango[i][j] = cango[j][i] = cnp2(0 , min(w , h) , j , i);
}
}
for(int i = 1 ; i <= 4 ; i++) cango[i][i] = square[i];
for(int k = 1 ; k <= 4 ; k++){
for(int i = 1 ; i <= 4 ; i++){
for(int j = 1 ; j <= 4 ; j++) maximize(cango[i][j] , min(cango[i][k] , cango[k][j]));
}
}
while(m--){
int x , r;
cin >> r >> x;
for(int i = 1 ; i <= 4 ; i++){
if(cango[i][x] >= r) cout << i;
}
cout << '\n';
}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
file(task);
file(tsk);
int T = 1;
// cin >> T;
while(T--)
{
Solve();
}
cerr << "Time elapsed: " << Times << " s.\n";
return 0;
}
// author: thefless
// I love Kim Anh
Compilation message
park.cpp: In function 'int cnp1(int, int, int)':
park.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int mid = l + r >> 1;
| ~~^~~
park.cpp: In function 'int cnp2(int, int, int, int)':
park.cpp:119:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
119 | int mid = l + r >> 1;
| ~~^~~
park.cpp: In function 'int main()':
park.cpp:16:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:163:5: note: in expansion of macro 'file'
163 | file(task);
| ^~~~
park.cpp:16:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:163:5: note: in expansion of macro 'file'
163 | file(task);
| ^~~~
park.cpp:16:125: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:163:5: note: in expansion of macro 'file'
163 | file(task);
| ^~~~
park.cpp:16:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:164:5: note: in expansion of macro 'file'
164 | file(tsk);
| ^~~~
park.cpp:16:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:164:5: note: in expansion of macro 'file'
164 | file(tsk);
| ^~~~
park.cpp:16:125: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:164:5: note: in expansion of macro 'file'
164 | file(tsk);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1286 ms |
2816 KB |
Output is correct |
| 2 |
Incorrect |
1254 ms |
2820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
3164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1286 ms |
2816 KB |
Output is correct |
| 2 |
Incorrect |
1254 ms |
2820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
