| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 484679 |
2021-11-05T03:43:06 Z |
minhcool |
Park (BOI16_park) |
C++17 |
|
1828 ms |
73564 KB |
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 2011;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, q, w, h;
long double x[N], y[N], r[N];
long double need[N][N];
vector<int> Adj[N];
bool vis[N];
long double req[N][N];
bool ck(int u, int v, long double z){
for(int i = 1; i <= n + 4; i++) Adj[i].clear();
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(need[i][j] <= z){
Adj[i].pb(j);
Adj[j].pb(i);
}
}
}
for(int i = 1; i <= n; i++){
if(x[i] <= (r[i] + z)){
Adj[i].pb(n + 1);
Adj[n + 1].pb(i);
}
}
for(int i = 1; i <= n; i++){
if(y[i] >= (h - r[i] - z)){
Adj[i].pb(n + 2);
Adj[n + 2].pb(i);
}
}
for(int i = 1; i <= n; i++){
if(x[i] >= (w - r[i] - z)){
Adj[i].pb(n + 3);
Adj[n + 3].pb(i);
}
}
for(int i = 1; i <= n; i++){
if(y[i] <= (r[i] + z)){
Adj[i].pb(n + 4);
Adj[n + 4].pb(i);
}
}
/*
cout << z << "\n";
for(auto it : Adj[n + 1]) cout << it << " ";
cout << "\n";
for(auto it : Adj[n + 2]) cout << it << " ";
cout << "\n";
for(auto it : Adj[n + 3]) cout << it << " ";
cout << "\n";
for(auto it : Adj[n + 4]) cout << it << " ";
cout << "\n";
*/
queue<int> bfs;
for(int i = 1; i <= n + 4; i++) vis[i] = 0;
vis[u] = 1;
bfs.push(u);
while(!bfs.empty()){
int x = bfs.front();
//if(u == 7 && v == 8) cout << z << " " << u << " " << x << "\n";
bfs.pop();
for(auto y : Adj[x]){
if(vis[y]) continue;
vis[y] = 1;
bfs.push(y);
}
}
return (vis[v] == 1);
}
int temp[5];
void process(){
temp[1] = 1, temp[2] = 4, temp[3] = 3, temp[4] = 2;
cin >> n >> q;
cin >> w >> h;
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i] >> r[i];
}
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
int temp = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
need[i][j] = sqrt((long double)temp);
need[i][j] -= r[i] + r[j];
need[i][j] = max(need[i][j], (long double)0.0);
need[i][j] /= 2.0;
}
}
for(int i = n + 1; i <= n + 4; i++){
for(int j = i + 1; j <= n + 4; j++){
long double l = 0, r = max(w, h);
while((r - l) >= 0.1){
long double mid = (l + r) / 2.0;
if(!ck(i, j, mid)) l = mid;
else r = mid;
}
//cout << i << " " << j << " " << l << "\n";
req[i][j] = req[j][i] = l;
}
}
while(q--){
long double r;
int k;
cin >> r >> k;
for(int i = 1; i <= 4; i++){
if(k == i){cout << i;}
else{
bool ck = 1;
if((((i - 1) / 2) != ((k - 1) / 2)) && req[n + 1][n + 3] < r) ck = 0;
if((i + k) != 5 && req[n + 2][n + 4] < r) ck = 0;
//cout << k << " " << i << " " << ck << "\n";
if(req[n + temp[i]][n + ((temp[i] + 2) % 4) + 1] < r) ck = 0;
//cout << k << " " << i << " " << req[n + i][n + ((i + 2) % 4) + 1] << " " << ck << "\n";
if(req[n + temp[k]][n + ((temp[k] + 2) % 4) + 1] < r) ck = 0;
//cout << i << " " << ((i + 2) % 4) + 1 << "\n";
if(ck) cout << i;
}
}
cout << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1779 ms |
73564 KB |
Output is correct |
| 2 |
Correct |
1801 ms |
73168 KB |
Output is correct |
| 3 |
Incorrect |
1828 ms |
73540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
194 ms |
2444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1779 ms |
73564 KB |
Output is correct |
| 2 |
Correct |
1801 ms |
73168 KB |
Output is correct |
| 3 |
Incorrect |
1828 ms |
73540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
