| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1018026 |
2024-07-09T13:01:01 Z |
m5588ohammed |
Park (BOI16_park) |
C++14 |
|
642 ms |
1872 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int UP,DOWN,RIGHT,LEFT,mx[5][5];
int n,m,t,v;
int parent[2005];
vector <array<int,3>> rad;
void make_set(int i){
parent[i]=i;
return;
}
int find(int a){
if(parent[a]==a) return a;
else return parent[a]=find(parent[a]);
}
void merge(int a,int b){
a=find(a),b=find(b);
parent[b]=a;
return;
}
bool UP_DOWN(){ return find(UP)==find(DOWN);}
bool UP_RIGHT(){ return find(UP)==find(RIGHT);}
bool UP_LEFT(){ return find(UP)==find(LEFT);}
bool DOWN_LEFT(){ return find(DOWN)==find(LEFT);}
bool DOWN_RIGHT(){ return find(DOWN)==find(RIGHT);}
bool LEFT_RIGHT(){ return find(LEFT)==find(RIGHT);}
void make(int k){
for(int i=0;i<=LEFT;i++) make_set(i);
for(int i=0;i<t;i++){
auto [x1,y1,r1]=rad[i];
for(int j=i+1;j<t;j++){
auto [x2,y2,r2]=rad[j];
if((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<=(r1+r2+k)*(r1+r2+k)) merge(i,j);
}
if(x1-r1-k<=0) merge(LEFT,i);
if(x1+r1+k>=n) merge(RIGHT,i);
if(y1-r1-k<=0) merge(UP,i);
if(y1+r1+k>=m) merge(DOWN,i);
}
}
int solve(int st,int en){
int l=0,r=1e9,ans=0;
while(l<=r){
int k=(l+r)/2;
make(k);
if(st==1&&en==4){
if(LEFT_RIGHT()==1||UP_LEFT()==1||DOWN_LEFT()==1) r=k-1;
else{ans=k;l=k+1;}
}
if(st==2&&en==4){
if(LEFT_RIGHT()==1||UP_DOWN()==1||UP_LEFT()==1||DOWN_RIGHT()==1) r=k-1;
else{ans=k;l=k+1;}
}
if(st==3&&en==4){
if(UP_DOWN()==1||UP_LEFT()==1||UP_RIGHT()==1) r=k-1;
else{ans=k;l=k+1;}
}
if(st==1&&en==2){
if(DOWN_LEFT()==1||UP_DOWN()==1||DOWN_RIGHT()==1) r=k-1;
else{ans=k;l=k+1;}
}
if(st==1&&en==3){
if(LEFT_RIGHT()==1||UP_DOWN()==1||DOWN_LEFT()==1||UP_RIGHT()==1) r=k-1;
else{ans=k;l=k+1;}
}
if(st==2&&en==3){
if(LEFT_RIGHT()==1||DOWN_RIGHT()==1||UP_RIGHT()==1) r=k-1;
else{ans=k;l=k+1;}
}
}
return ans;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>t>>v>>n>>m;
for(int i=0;i<t;i++){
int x,y,r;
cin>>x>>y>>r;
rad.push_back({x,y,r});
}
UP=t+1,DOWN=t+2,RIGHT=t+3,LEFT=t+4;
for(int d1=1;d1<=4;d1++) for(int d2=d1+1;d2<=4;d2++) mx[d1][d2]=solve(d1,d2);
// cout<<mx[1][2]<<endl;
// cout<<mx[1][3]<<endl;
// cout<<mx[1][4]<<endl;
//cout<<mx[2][3]<<endl;
// cout<<mx[2][4]<<endl;
// cout<<mx[3][4]<<endl;
while(v--){
int st,r;
cin>>r>>st;
vector <int> ans;
ans.push_back(st);
if(mx[min(st,1ll)][max(st,1ll)]>=r*2) ans.push_back(1);
if(mx[min(st,2ll)][max(st,2ll)]>=r*2) ans.push_back(2);
if(mx[min(st,3ll)][max(st,3ll)]>=r*2) ans.push_back(3);
if(mx[min(st,4ll)][max(st,4ll)]>=r*2) ans.push_back(4);
sort(ans.begin(),ans.end());
for(int i:ans) cout<<i;
cout<<endl;
}
return 0;
}
Compilation message
park.cpp: In function 'void make(long long int)':
park.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
32 | auto [x1,y1,r1]=rad[i];
| ^
park.cpp:34:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | auto [x2,y2,r2]=rad[j];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
613 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
642 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
1872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
613 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
642 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
