Submission #781032

#	Time	Username	Problem	Language	Result	Execution time	Memory
781032		1075508020060209tc	Park (BOI16_park)	C++14	100 / 100	782 ms	111092 KiB

park

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
 
int n;int m;
int H;int W;
int uf[5010];
int fin(int x){
if(uf[x]==x){return x;}
uf[x]=fin(uf[x]);
return uf[x];
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){return;}
uf[pa]=pb;
}
int xar[200005];int yar[200005];int rar[200005];
int ent[200005];int fat[200005];
set<int>ans[200005];
 
int iso(int st){
int b=st+1;
if(b==5){b=1;}
if(fin(st)==fin(b)){return 1;}
return 0;
}
 
void chk(int id){
int st=ent[id];
ans[id].insert(st);
if(iso(st)){return;}
for(int i=1;i<=4;i++){
    if(i==st){continue;}
    if(iso(i)){continue;}
    if( ((st==1||st==4)&&(i==3||i==2)) ){
        if(fin(4)==fin(2)){continue;}
    }
    if( ((i==1||i==4)&&(st==3||st==2)) ){
        if(fin(4)==fin(2)){continue;}
    }
    if( ((st==1||st==2)&&(i==3||i==4)) ){
        if(fin(1)==fin(3)){continue;}
    }
    if( ((i==1||i==2)&&(st==3||st==4)) ){
        if(fin(1)==fin(3)){continue;}
    }
    ans[id].insert(i);
}
}
 
int sqt(int v){
int l=0;int r=1500000000;
while(l<r){
    int mi=l+(r-l+1)/2;
    if( mi*mi<=v ){
        l=mi;
    }else{
        r=mi-1;
    }
}
return l;
 
}
 
 
signed main(){
cin>>n>>m>>W>>H;
//swap(W,H);
for(int i=1;i<=n+4;i++){
    uf[i]=i;
}
n+=4;
for(int i=5;i<=n;i++){
    cin>>xar[i]>>yar[i]>>rar[i];
    //if(rar[i]<=0){return 2;}
}
for(int i=1;i<=m;i++){
    cin>>fat[i]>>ent[i];
    //if(fat[i]<=0){return 2;}
}
vector<pair<long long,pair<int,int>>>event;
 
for(int i=5;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        //if(i==j){continue;}
        long long v=(xar[i]-xar[j])*(xar[i]-xar[j])+(yar[i]-yar[j])*(yar[i]-yar[j]);
        long long d=sqt(v);
       // if( (d*d)!=v ){
         //   d++;
        //}
 
        d-=rar[i]+rar[j];
        event.push_back({d,{i,j}});
    }
}
 
for(int i=5;i<=n;i++){
    long long d=xar[i]-rar[i];
    event.push_back({d,{1,i}});
}
for(int i=5;i<=n;i++){
    long long d=yar[i]-rar[i];
    event.push_back({d,{2,i}});
}
for(int i=5;i<=n;i++){
    long long d=W-xar[i]-rar[i];
    event.push_back({d,{3,i}});
}
for(int i=5;i<=n;i++){
    long long d=H-yar[i]-rar[i];
    event.push_back({d,{4,i}});
}
for(int i=1;i<=m;i++){
    event.push_back({fat[i]*2,{-1,i}});
}
sort(event.begin(),event.end());
 
for(int i=0;i<event.size();i++){
    if(event[i].second.first<=n&&event[i].second.first>=1){
        mrg(event[i].second.first,event[i].second.second);
    }else{
        chk(event[i].second.second);
    }
}
for(int i=1;i<=m;i++){
    for(auto it=ans[i].begin();it!=ans[i].end();it++){
        cout<<(*it);
    }cout<<endl;
}
 
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:121:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 | for(int i=0;i<event.size();i++){
      |             ~^~~~~~~~~~~~~

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