이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 2005
struct A{
long long a,b,r,st;
bool operator<(const A& o)const{
return r<o.r;
}
};
struct B{
long long r,e,id;
bool operator<(const B& o)const{
return r<o.r;
}
};
int p[N],bit[N],ans[100005];
long long x[N],y[N],r[N];
vector<A> edge;
vector<B> op;
bitset<20> vis,ok[5];
int fp(int v){return v==p[v]?v:p[v]=fp(p[v]);}
int dis(int i,int j){
double a=x[i]-x[j],b=y[i]-y[j],sq=sqrt(a*a+b*b);
return (long long)(floor(sq))-r[i]-r[j];
}
void add(int id){
auto [a,b,r,st]=edge[id];
if(!st){
bit[fp(a)]|=bit[fp(b)];
p[fp(b)]=fp(a);
}
else bit[fp(a)]|=st;
if(!vis[bit[fp(a)]]){
int i,j;
b=bit[fp(a)];
vis[bit[fp(a)]]=true;
for(i=0;i<4;i++){
if((b&(1<<i))&&(b&(1<<((i+1)%4)))){
for(j=0;j<4;j++){
if(i!=j)ok[i+1][j+1]=ok[j+1][i+1]=false;
}
}
}
if((b&1)&&(b&4))ok[1][4]=ok[4][1]=ok[1][3]=ok[3][1]=ok[4][2]=ok[2][4]=ok[2][3]=ok[3][2]=false;
if((b&2)&&(b&8))ok[1][2]=ok[2][1]=ok[1][3]=ok[3][1]=ok[4][2]=ok[2][4]=ok[4][3]=ok[3][4]=false;
}
}
int main(){
int n,m,w,h,i,j,now,val;
long long radius,e;
scanf("%d %d %d %d",&n,&m,&w,&h);
iota(p,p+n+1,0);
for(i=1;i<=n;i++){
scanf("%lld %lld %lld",&x[i],&y[i],&r[i]);
}
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
edge.push_back({i,j,dis(i,j),0});
}
}
for(i=1;i<=n;i++){
edge.push_back({i,0,x[i]-r[i],1});
edge.push_back({i,0,y[i]-r[i],2});
edge.push_back({i,0,w-x[i]-r[i],4});
edge.push_back({i,0,h-y[i]-r[i],8});
}
for(i=1;i<=4;i++)for(j=1;j<=4;j++)ok[i][j]=true;
sort(edge.begin(),edge.end());
for(i=1;i<=m;i++)scanf("%lld %lld",&radius,&e),op.push_back({2*radius,e,i});
sort(op.begin(),op.end());
now=0;
for(auto [rad,e,id]:op){
while(now<edge.size()&&edge[now].r<rad)add(now++);
val=0;
for(i=1;i<=4;i++)if(ok[e][i])val=val*10+i;
ans[id]=val;
}
for(i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
컴파일 시 표준 에러 (stderr) 메시지
park.cpp: In function 'int main()':
park.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<A>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | while(now<edge.size()&&edge[now].r<rad)add(now++);
| ~~~^~~~~~~~~~~~
park.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d %d %d %d",&n,&m,&w,&h);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%lld %lld %lld",&x[i],&y[i],&r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:78:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | for(i=1;i<=m;i++)scanf("%lld %lld",&radius,&e),op.push_back({2*radius,e,i});
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |