oj.uz

답안 #780812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780812 2023-07-12T13:27:56 Z 1075508020060209tc Park (BOI16_park) C++14
0 / 100
 287 ms 59156 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
//#define long
long double eps=0.0000001;
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< 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]);
         double d=sqrt(v);
        d-=rar[i]+rar[j];
        event.push_back({d,{i,j}});
    }
}
for(int i=5;i<=n;i++){
     double d=xar[i]-rar[i];
    event.push_back({d,{1,i}});
}
for(int i=5;i<=n;i++){
    double d=yar[i]-rar[i];
    event.push_back({d,{2,i}});
}
for(int i=5;i<=n;i++){
    double d=W-xar[i]-rar[i];
    event.push_back({d,{3,i}});
}
for(int i=5;i<=n;i++){
    double 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.+eps,{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:100:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 | for(int i=0;i<event.size();i++){
      |             ~^~~~~~~~~~~~~

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 59156 KB Output is correct
2 Correct 287 ms 59136 KB Output is correct
3 Incorrect 261 ms 59144 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 27504 KB Output is correct
2 Incorrect 206 ms 27596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 59156 KB Output is correct
2 Correct 287 ms 59136 KB Output is correct
3 Incorrect 261 ms 59144 KB Output isn't correct
4 Halted 0 ms 0 KB -