Submission #586661

#	Time	Username	Problem	Language	Result	Execution time	Memory
586661		krit3379	Park (BOI16_park)	C++17	0 / 100	331 ms	66176 KiB

park

#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
*/

Compilation message (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});
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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