| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1018137 |
2024-07-09T15:14:28 Z |
m5588ohammed |
Park (BOI16_park) |
C++14 |
|
1771 ms |
1848 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[2010];
vector <array<__int128,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((__int128)((__int128)(x2-x1)*(__int128)(x2-x1)+((__int128)y2-y1)*(__int128)(y2-y1))<=(__int128)((__int128)(r1+r2+k)*(__int128)(r1+r2+k))) merge(i,j);
}
if((__int128)x1-r1-k<=0) merge(LEFT,i);
if((__int128)x1+r1+k>=n) merge(RIGHT,i);
if((__int128)y1-r1-k<=0) merge(UP,i);
if((__int128)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({(__int128)x,(__int128)y,(__int128)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);
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 |
1712 ms |
696 KB |
Output is correct |
| 2 |
Incorrect |
1771 ms |
692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
1848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1712 ms |
696 KB |
Output is correct |
| 2 |
Incorrect |
1771 ms |
692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
