oj.uz

Submission #780825

# Submission time Handle Problem Language Result Execution time Memory
780825 2023-07-12T13:37:16 Z 1075508020060209tc Park (BOI16_park) C++14
0 / 100
 453 ms 75536 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
//#define double long long
//#define long
long double eps=-0.001;
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){st=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);
}

}

signed main(){
cin>>n>>m>>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];
}
for(int i=1;i<=m;i++){
    cin>>fat[i]>>ent[i];
}
vector<pair<long double,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 double d=sqrt(v);
        d-=rar[i]+rar[j];
        event.push_back({d,{i,j}});
    }
}
for(int i=5;i<=n;i++){
    long double d=xar[i]-rar[i];
    event.push_back({d,{1,i}});
}
for(int i=5;i<=n;i++){
    long double d=yar[i]-rar[i];
    event.push_back({d,{2,i}});
}
for(int i=5;i<=n;i++){
    long double d=W-xar[i]-rar[i];
    event.push_back({d,{3,i}});
}
for(int i=5;i<=n;i++){
    long double d=H-yar[i]-rar[i];
    event.push_back({d,{4,i}});
}
for(int i=1;i<=m;i++){
    long double v=fat[i]+fat[i];v+=eps;
    event.push_back({v,{1000000000,i}});
}
sort(event.begin(),event.end());

for(int i=0;i<event.size();i++){
    if(event[i].second.first<=n){
        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

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

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 75472 KB Output is correct
2 Correct 381 ms 75536 KB Output is correct
3 Incorrect 453 ms 75464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 28436 KB Output is correct
2 Incorrect 225 ms 28628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 75472 KB Output is correct
2 Correct 381 ms 75536 KB Output is correct
3 Incorrect 453 ms 75464 KB Output isn't correct
4 Halted 0 ms 0 KB -