Submission #1183916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183916		sasde	Park (BOI16_park)	C++20	0 / 100	232 ms	49776 KiB

park

#include<bits/stdc++.h>
#define int long long 
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
using namespace std;
const int NN=1e5,N=2e3+5,lg=20,mod=1e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int n,m,w,h;
long long k[5][5];
struct pt
{
   int x,y,r;  
}a[N];
vector<pt>res;
long long  qq(int i,int j){
  return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))-a[i].r-a[j].r;
}
int r[N];
int acs(int u){
  return r[u]==u?u:r[u]=acs(r[u]);
}
void join(int u,int v){
  u=acs(u);
  v=acs(v);
  if(u!=v){
    r[v]=u;
  }
}
void solve(){
  cin >> n >> m >> w >> h;
  for(int i=1;i<=n;++i){
    cin >> a[i].x >> a[i].y >> a[i].r;
    res.pb({1,i+4,h-a[i].y-a[i].r});
    res.pb({2,i+4,w-a[i].x-a[i].r});
    res.pb({3,i+4,a[i].y-a[i].r});
    res.pb({4,i+4,a[i].x-a[i].r});
  }
  for(int i=1;i<=n+4;++i)r[i]=i;
  for(int i=1;i<=4;++i)for(int j=1;j<=4;++j)k[i][j]=-1e18;
  for(int i=5;i<=n+4;++i){
    for(int j=5;j<i;++j){
      res.pb({i,j,qq(i-4,j-4)});
    }
  }
  sort(res.begin(),res.end(),[](pt x,pt y){
    return x.r<y.r;
  });
  for(pt x:res){
    join(x.x,x.y);
    // cout <<x.x<<" "<<x.y<<" "<<x.r<<'\n';
    for(int i=1;i<=4;++i){
      for(int j=i+1;j<=4;++j){
        if(k[i][j]==-1e18&&acs(i)==acs(j))
          k[i][j]=x.r,k[j][i]=x.r;
      }
    }
  }
  // for(int i=1;i<=4;++i){for(int j=1;j<=4;++j)cout <<k[i][j]<<" ";cout<<'\n';}

  for(int i=1;i<=m;++i){
    int x,r;
    cin >>r >> x;r*=2;
    for(int j=1;j<=4;++j){
      if(j!=x){
        // cout <<k[x][j]<<" ";
        if(k[x][j]>=r)cout <<j;
      }
    else cout <<j;
    }cout <<'\n';

  }

   
}
main()
{
  srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    int t=1;
 //   cin >> t;
while(t--){
    solve();
}

}

Compilation message (stderr)

park.cpp:92:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main()
      | ^~~~
park.cpp: In function 'int main()':
park.cpp:99:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
park.cpp:100:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42