oj.uz

Submission #781032

# Submission time Handle Problem Language Result Execution time Memory
781032 2023-07-12T16:09:38 Z 1075508020060209tc Park (BOI16_park) C++14
100 / 100
 782 ms 111092 KB 
#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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 59148 KB Output is correct
2 Correct 538 ms 59148 KB Output is correct
3 Correct 528 ms 59124 KB Output is correct
4 Correct 534 ms 59120 KB Output is correct
5 Correct 537 ms 59148 KB Output is correct
6 Correct 547 ms 59128 KB Output is correct
7 Correct 484 ms 59172 KB Output is correct
8 Correct 498 ms 59144 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 27628 KB Output is correct
2 Correct 193 ms 25632 KB Output is correct
3 Correct 210 ms 26556 KB Output is correct
4 Correct 192 ms 26684 KB Output is correct
5 Correct 196 ms 26936 KB Output is correct
6 Correct 222 ms 29568 KB Output is correct
7 Correct 185 ms 24520 KB Output is correct
8 Correct 181 ms 24532 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 59148 KB Output is correct
2 Correct 538 ms 59148 KB Output is correct
3 Correct 528 ms 59124 KB Output is correct
4 Correct 534 ms 59120 KB Output is correct
5 Correct 537 ms 59148 KB Output is correct
6 Correct 547 ms 59128 KB Output is correct
7 Correct 484 ms 59172 KB Output is correct
8 Correct 498 ms 59144 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 205 ms 27628 KB Output is correct
12 Correct 193 ms 25632 KB Output is correct
13 Correct 210 ms 26556 KB Output is correct
14 Correct 192 ms 26684 KB Output is correct
15 Correct 196 ms 26936 KB Output is correct
16 Correct 222 ms 29568 KB Output is correct
17 Correct 185 ms 24520 KB Output is correct
18 Correct 181 ms 24532 KB Output is correct
19 Correct 749 ms 110904 KB Output is correct
20 Correct 729 ms 110988 KB Output is correct
21 Correct 782 ms 110932 KB Output is correct
22 Correct 729 ms 111000 KB Output is correct
23 Correct 776 ms 110932 KB Output is correct
24 Correct 703 ms 111092 KB Output is correct