| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 932683 |
2024-02-24T03:11:49 Z |
abcdehello |
Park (BOI16_park) |
C++17 |
|
235 ms |
52412 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<double,pll> pdll;
#define f first
#define s second
struct tree{
ll x,y,r;
};
double dist(tree a,tree b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double spaceBetween(tree a,tree b){
return max(0.0,dist(a,b)-a.r-b.r);
}
ll n,m,w,h,p[2050];
tree t[2050];
vector<int> ans[100050];
vector<pdll> sep;
vector<pair<pll,ll>> qry;
int find(int u){
if (u!=p[u]) p[u]=find(p[u]);
return p[u];
}
bool isConnected(int u,int v){
return find(u)==find(v);
}
int main(){
cin >> n >> m;
cin >> w >> h;
for (int i=1;i<=n+4;i++) p[i]=i;
for (int i=1;i<=n;i++){
cin >> t[i].x >> t[i].y >> t[i].r;
}
for (int i=1;i<=m;i++){
int e,r;
cin >> r >> e;
qry.push_back({{r,e},i});
}
for (int i=1;i<=n;i++){
for (int j=i+1;j<=n;j++) sep.push_back({spaceBetween(t[i],t[j]),{i,j}});
}
for (int i=1;i<=n;i++){
sep.push_back({t[i].x-t[i].r,{i,n+1}});//left
sep.push_back({t[i].y-t[i].r,{i,n+2}});//down
sep.push_back({w-t[i].x-t[i].r,{i,n+3}});//right
sep.push_back({h-t[i].y-t[i].r,{i,n+4}});//up
}
sort(sep.begin(),sep.end());
sort(qry.begin(),qry.end());
int nxt=0;
for (auto q:qry){
//while (sep[nxt].f<2*q.f.f) cerr << "*" << sep[nxt].f << endl,p[find(sep[nxt].s.f)]=find(sep[nxt].s.s),nxt++;
int ind=q.s,e=q.f.s;
ans[ind].push_back(e);
//cerr << ind << " " << e << " " << q.f.f << endl;
if (e==1){
//cerr << 1 << endl;
if (!isConnected(n+1,n+2)&&!isConnected(n+2,n+3)&&!isConnected(n+2,n+4)) ans[ind].push_back(2);
if (!isConnected(n+1,n+2)&&!isConnected(n+3,n+4)&&!isConnected(n+1,n+3)&&!isConnected(n+2,n+4)) ans[ind].push_back(3);
if (!isConnected(n+1,n+2)&&!isConnected(n+1,n+4)&&!isConnected(n+1,n+3)) ans[ind].push_back(4);
}
else if (e==2){
//cerr << 2 << endl;
if (!isConnected(n+2,n+3)&&!isConnected(n+3,n+4)&&!isConnected(n+3,n+1)) ans[ind].push_back(3);
if (!isConnected(n+2,n+3)&&!isConnected(n+4,n+1)&&!isConnected(n+2,n+4)&&!isConnected(n+3,n+1)) ans[ind].push_back(4);
if (!isConnected(n+2,n+3)&&!isConnected(n+2,n+1)&&!isConnected(n+2,n+4)) ans[ind].push_back(1);
}
else if (e==3){
//cerr << 3 << endl;
if (!isConnected(n+3,n+4)&&!isConnected(n+4,n+1)&&!isConnected(n+4,n+2)) ans[ind].push_back(4);
if (!isConnected(n+3,n+4)&&!isConnected(n+1,n+2)&&!isConnected(n+3,n+1)&&!isConnected(n+2,n+4)) ans[ind].push_back(1);
if (!isConnected(n+3,n+4)&&!isConnected(n+3,n+2)&&!isConnected(n+3,n+1)) ans[ind].push_back(2);
}
else{
//cerr << 4 << endl;
if (!isConnected(n+4,n+1)&&!isConnected(n+1,n+2)&&!isConnected(n+1,n+3)) ans[ind].push_back(1);
if (!isConnected(n+4,n+1)&&!isConnected(n+2,n+3)&&!isConnected(n+4,n+2)&&!isConnected(n+2,n+4)) ans[ind].push_back(2);
if (!isConnected(n+4,n+1)&&!isConnected(n+4,n+3)&&!isConnected(n+4,n+2)) ans[ind].push_back(3);
}
}
for (int i=1;i<=n;i++) sort(ans[i].begin(),ans[i].end());
for (int i=1;i<=n;i++){
for (int j:ans[i]) cout << j;
cout << "\n";
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:52:6: warning: unused variable 'nxt' [-Wunused-variable]
52 | int nxt=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
235 ms |
52412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
9152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
235 ms |
52412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
