| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 670753 |
2022-12-10T08:52:58 Z |
berr |
Park (BOI16_park) |
C++17 |
|
1456 ms |
596 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> tx(2005), ty(2005), tr(2005), vis(2005);
int dist[4][4];
queue<int> q;
int check(int a, int b, int s){
int h=(tx[a]-tx[b]);
int e=(ty[a]-ty[b]);
h*=h; e*=e;
h+=e;
int f=2*s+tr[a]+tr[b];
if((f*f)>h) return 1;
return 0;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m; cin >> n >> m;
int x, y; cin >> x >> y;
for(int i=0; i<n; i++){
cin>>tx[i]>>ty[i]>>tr[i];
}
int s=0;
//l u
for(int i=30; i>=0; i--){
int tmp = s+(1<<i);
for(int l=0; l<n; l++)
{
vis[l]=0;
if((tx[l]-tr[l])<tmp*2){
q.push(l);
}
}
while(q.size())
{
int v=q.front(); vis[v]=1;
q.pop();
for(int l=0; l<n; l++)
{
if(!vis[l]&&check(l, v, tmp))
{
vis[l]=1;
q.push(l);
}
}
}
int flag=1;
for(int l=0; l<n; l++){
if(!vis[l]) continue;
if(y-ty[l]-tr[l]<2*tmp) flag=0;
}
if(flag) s=tmp;
}
dist[0][1]=dist[1][0]=s+1;
s=0;
// l, r;
for(int i=30; i>=0; i--){
int tmp = s+(1<<i);
for(int l=0; l<n; l++)
{
vis[l]=0;
if((tx[l]-tr[l])<tmp*2){
q.push(l);
}
}
while(q.size())
{
int v=q.front(); vis[v]=1;
q.pop();
for(int l=0; l<n; l++)
{
if(!vis[l]&&check(l, v, tmp))
{
vis[l]=1;
q.push(l);
}
}
}
int flag=1;
for(int l=0; l<n; l++){
if(!vis[l]) continue;
if(x-tx[l]-tr[l]<2*tmp) flag=0;
}
if(flag) s=tmp;
}
dist[0][2]=dist[2][0]=s+1;
s=0;
//l, d
for(int i=30; i>=0; i--){
int tmp = s+(1<<i);
for(int l=0; l<n; l++)
{
vis[l]=0;
if((tx[l]-tr[l])<tmp*2){
q.push(l);
}
}
while(q.size())
{
int v=q.front(); vis[v]=1;
q.pop();
for(int l=0; l<n; l++)
{
if(!vis[l]&&check(l, v, tmp))
{
vis[l]=1;
q.push(l);
}
}
}
int flag=1;
for(int l=0; l<n; l++){
if(!vis[l]) continue;
if(ty[l]-ty[l]<2*tmp) flag=0;
}
if(flag) s=tmp;
}
dist[0][3]=dist[3][0]=s+1;
s=0;
//u, r
for(int i=30; i>=0; i--){
int tmp = s+(1<<i);
for(int l=0; l<n; l++)
{
vis[l]=0;
if(y-ty[l]-tr[l]<tmp*2){
q.push(l);
}
}
while(q.size())
{
int v=q.front(); vis[v]=1;
q.pop();
for(int l=0; l<n; l++)
{
if(!vis[l]&&check(l, v, tmp))
{
vis[l]=1;
q.push(l);
}
}
}
int flag=1;
for(int l=0; l<n; l++){
if(!vis[l]) continue;
if(x-tx[l]-tr[l]<2*tmp) flag=0;
}
if(flag) s=tmp;
}
dist[1][2]=dist[2][1]=s+1;
s=0;
//u, d
for(int i=30; i>=0; i--){
int tmp = s+(1<<i);
for(int l=0; l<n; l++)
{
vis[l]=0;
if(y-ty[l]-tr[l]<tmp*2){
q.push(l);
}
}
while(q.size())
{
int v=q.front(); vis[v]=1;
q.pop();
for(int l=0; l<n; l++)
{
if(!vis[l]&&check(l, v, tmp))
{
vis[l]=1;
q.push(l);
}
}
}
int flag=1;
for(int l=0; l<n; l++){
if(!vis[l]) continue;
if(ty[l]-ty[l]<2*tmp) flag=0;
}
if(flag) s=tmp;
}
dist[1][3]=dist[3][1]=s+1;
s=0;
// r, d;
for(int i=30; i>=0; i--){
int tmp = s+(1<<i);
for(int l=0; l<n; l++)
{
vis[l]=0;
if(x-tx[l]-tr[l]<2*tmp) q.push(l);
}
while(q.size())
{
int v=q.front(); vis[v]=1;
q.pop();
for(int l=0; l<n; l++)
{
if(!vis[l]&&check(l, v, tmp))
{
vis[l]=1;
q.push(l);
}
}
}
int flag=1;
for(int l=0; l<n; l++){
if(!vis[l]) continue;
if(ty[l]-ty[l]<2*tmp) flag=0;
}
if(flag) s=tmp;
}
dist[2][3]=dist[3][2]=s+1;
for(int i=0; i<m; i++)
{
int t, s; cin>>s>>t;
string ans;
if(t==1){
ans+='1';
if(min({dist[0][3], dist[1][3], dist[2][3]})>=s) ans+='2';
if(min({dist[0][2], dist[0][3], dist[1][3], dist[1][2]})>=s) ans+='3';
if(min({dist[0][3], dist[0][2], dist[0][1]})>=s) ans+='4';
}
if(t==2){
if(min({dist[0][3], dist[1][3], dist[2][3]})>=s) ans+='1';
ans+='2';
if(min({dist[2][1], dist[2][3], dist[2][0]})>=s) ans+='3';
if(min({dist[0][1], dist[0][2], dist[1][3], dist[2][3]})>=s) ans+='4';
}
if(t==3){
if(min({dist[0][2], dist[0][3], dist[1][3], dist[1][2]})>=s) ans+='1';
if(min({dist[2][1], dist[2][3], dist[2][0]})>=s) ans+='2';
ans+='3';
if(min({dist[1][3], dist[1][2], dist[1][0]})>=s) ans+='4';
}
if(t==4){
if(min({dist[0][3], dist[0][2], dist[0][1]})>=s) ans+='1';
if(min({dist[0][1], dist[0][2], dist[1][3], dist[2][3]})>=s) ans+='2';
if(min({dist[1][3], dist[1][2], dist[1][0]})>=s) ans+='3';
ans+='4';
}
cout<<ans<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1456 ms |
404 KB |
Output is correct |
| 2 |
Incorrect |
1427 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1456 ms |
404 KB |
Output is correct |
| 2 |
Incorrect |
1427 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
