| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 935663 |
2024-02-29T10:51:54 Z |
tosivanmak |
Park (BOI16_park) |
C++17 |
|
269 ms |
61764 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
ll n,m;
struct edge{
ll u,v,dist;
bool operator<(const edge& e)const{
return dist<e.dist;
}
edge(ll _u, ll _v, ll _dist){
u=_u,v=_v,dist=_dist;
}
};
struct popo{
ll first,second,q;
bool operator<(const popo& p)const{
return first<p.first;
}
};
struct DSU{
vector<ll>fa,siz;
void init(ll n){
fa.resize(n+5);
siz.resize(n+5);
for(int i=1;i<=n;i++){
fa[i]=i,siz[i]=1;
}
}
ll root(ll x){
return (fa[x]==x ? x : fa[x]=root(fa[x]));
}
void unite(ll u, ll v){
fa[root(u)]=root(v);
}
}dd;
/*
n+1: left
n+2: up
n+3: right
n+4: down
*/
bool top_down(){
return (dd.root(n+2)==dd.root(n+4));
}
bool top_left(){
return (dd.root(n+2)==dd.root(n+1));
}
bool top_right(){
return (dd.root(n+2)==dd.root(n+3));
}
bool left_down(){
return (dd.root(n+1)==dd.root(n+4));
}
bool left_right(){
return (dd.root(n+1)==dd.root(n+3));
}
bool down_right(){
return (dd.root(n+4)==dd.root(n+3));
}
ll d(ll r, ll c, ll r2, ll c2, ll a, ll b){
ld tot=(r-r2)*(r-r2)+(c-c2)*(c-c2);
tot=sqrt(tot);
// cout<<tot<<" "<<a+b<<'\n';
tot-=(a+b);
tot/=2;
ll bruh=tot;
bruh++;
return bruh;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
ll x[n+5],y[n+5],r[n+5];
ll w,h;
cin>>w>>h;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>r[i];
}
vector<edge>v;
/*
n+1: left
n+2: up
n+3: right
n+4: down
*/
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
ll bruh=d(x[i],y[i],x[j],y[j],r[i],r[j]);
// cout<<bruh<<" ";
v.push_back({i,j,bruh});
}
}
for(int i=1;i<=n;i++){
ld bruh=x[i]-r[i];
bruh/=2;
ll store=bruh;
store++;
v.push_back({i,n+1,store});
}
for(int i=1;i<=n;i++){
ld bruh=y[i]-r[i];
bruh/=2;
ll store=bruh;
store++;
v.push_back({i,n+4,store});
}
for(int i=1;i<=n;i++){
ld bruh=h-y[i]-r[i];
bruh/=2;
ll store=bruh;
store++;
v.push_back({i,n+2,store});
}
for(int i=1;i<=n;i++){
ld bruh=w-x[i]-r[i];
bruh/=2;
ll store=bruh;
store++;
v.push_back({i,n+3,store});
}
dd.init(n+5);
sort(v.begin(),v.end());
ll cur=0;
ll ra[m+5],en[m+5];
vector<popo>fk;
for(int i=1;i<=m;i++){
cin>>ra[i]>>en[i];
fk.push_back({ra[i],en[i],i});
}
sort(fk.begin(),fk.end());
ll qry[m+5];
vector<ll>ans[m+5];
for(int i=1;i<=m;i++){
ra[i]=fk[i-1].first,en[i]=fk[i-1].second;
qry[i]=fk[i-1].q;
}
for(int i=1;i<=m;i++){
vector<ll>temp;
ll rad=ra[i],ent=en[i];
if(cur==v.size()-1){
}
else{
while(v[cur].dist<=rad){
dd.unite(v[cur].u,v[cur].v);
cur++;
if(cur==v.size()-1){
break;
}
}
for(int j=1;j<=4;j++){
if(j==ent){
temp.push_back(j);
}
else{
if(ent==1){
if(dd.root(n+1)==dd.root(n+4)){
}
else{
if(j==2){
if(!top_down()&&!down_right()){
temp.push_back(j);
}
}
if(j==3){
if(!top_right()&&!top_down()&&!left_right()){
temp.push_back(j);
}
}
if(j==4){
if(!left_right()&&!top_left()){
temp.push_back(j);
}
}
}
}
else if(ent==2){
if(down_right()){
}
else{
if(j==1){
if(!top_down()&&!left_down()){
temp.push_back(j);
}
}
else if(j==3){
if(!top_right()&&!left_right()){
temp.push_back(j);
}
}
else{
if(!top_left()&&!top_down()&&!left_right()){
temp.push_back(j);
}
}
}
}
else if(ent==3){
if(top_right()){
continue;
}
if(j==1){
if(!left_down()&&!left_right()&&!top_down()){
temp.push_back(j);
}
}
else if(j==2){
if(!down_right()&&!left_right()){
temp.push_back(j);
}
}
else{
if(!top_left()&&!top_down()){
temp.push_back(j);
}
}
}
else{
if(top_left()){
continue;
}
if(j==1){
if(!left_down()&&!left_right()){
temp.push_back(j);
}
}
else if(j==2){
if(!top_down()&&!left_right()&&!down_right()){
temp.push_back(j);
}
}
else{
if(!top_right()&&!top_down()){
temp.push_back(j);
}
}
}
}
}
}
ans[qry[i]]=temp;
}
for(int i=1;i<=m;i++){
for(auto& u: ans[i]){
cout<<u;
}
cout<<'\n';
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:144:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | if(cur==v.size()-1){
| ~~~^~~~~~~~~~~~
park.cpp:151:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | if(cur==v.size()-1){
| ~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
209 ms |
50712 KB |
Output is correct |
| 2 |
Correct |
196 ms |
51636 KB |
Output is correct |
| 3 |
Correct |
202 ms |
50408 KB |
Output is correct |
| 4 |
Correct |
194 ms |
50108 KB |
Output is correct |
| 5 |
Correct |
193 ms |
50880 KB |
Output is correct |
| 6 |
Correct |
194 ms |
51108 KB |
Output is correct |
| 7 |
Correct |
183 ms |
51124 KB |
Output is correct |
| 8 |
Correct |
182 ms |
49852 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
12852 KB |
Output is correct |
| 2 |
Correct |
49 ms |
13388 KB |
Output is correct |
| 3 |
Correct |
48 ms |
12860 KB |
Output is correct |
| 4 |
Correct |
53 ms |
12956 KB |
Output is correct |
| 5 |
Correct |
57 ms |
12784 KB |
Output is correct |
| 6 |
Correct |
51 ms |
13112 KB |
Output is correct |
| 7 |
Correct |
46 ms |
12620 KB |
Output is correct |
| 8 |
Correct |
42 ms |
12476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
209 ms |
50712 KB |
Output is correct |
| 2 |
Correct |
196 ms |
51636 KB |
Output is correct |
| 3 |
Correct |
202 ms |
50408 KB |
Output is correct |
| 4 |
Correct |
194 ms |
50108 KB |
Output is correct |
| 5 |
Correct |
193 ms |
50880 KB |
Output is correct |
| 6 |
Correct |
194 ms |
51108 KB |
Output is correct |
| 7 |
Correct |
183 ms |
51124 KB |
Output is correct |
| 8 |
Correct |
182 ms |
49852 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
55 ms |
12852 KB |
Output is correct |
| 12 |
Correct |
49 ms |
13388 KB |
Output is correct |
| 13 |
Correct |
48 ms |
12860 KB |
Output is correct |
| 14 |
Correct |
53 ms |
12956 KB |
Output is correct |
| 15 |
Correct |
57 ms |
12784 KB |
Output is correct |
| 16 |
Correct |
51 ms |
13112 KB |
Output is correct |
| 17 |
Correct |
46 ms |
12620 KB |
Output is correct |
| 18 |
Correct |
42 ms |
12476 KB |
Output is correct |
| 19 |
Correct |
269 ms |
61260 KB |
Output is correct |
| 20 |
Correct |
241 ms |
60828 KB |
Output is correct |
| 21 |
Correct |
253 ms |
61764 KB |
Output is correct |
| 22 |
Correct |
253 ms |
60832 KB |
Output is correct |
| 23 |
Correct |
249 ms |
60776 KB |
Output is correct |
| 24 |
Correct |
247 ms |
60968 KB |
Output is correct |
