oj.uz

Submission #1098788

# Submission time Handle Problem Language Result Execution time Memory
1098788 2024-10-10T01:33:45 Z Bananabread Park (BOI16_park) C++17
100 / 100
 349 ms 133036 KB 
#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname ""
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
struct pot{
    ll x,y,r;
} arr[2001];
ll ans[100001];
ll par[3001];
ll sz[3001];
ll find_par(ll x){
    return (x==par[x]? x: par[x]=find_par(par[x]));
}
void uni(ll a,ll b){
    a=find_par(a);
    b=find_par(b);
    if(a!=b){
        if(sz[a]<sz[b]) swap(a,b);
        sz[a]+=sz[b];
        par[b]=a;
    }
}
vector<array<ll,4>> sweep;
ll w,h,n,m;
ll dist(pot a,pot b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))-a.r-b.r;
}
bool check(ll st,ll ed){
    if(st>ed) swap(st,ed);
    if(st==ed) return 1;
    if(st==1){
        if(ed==2){
            if(find_par(n+1)==find_par(n+3)) return 0;
            if(find_par(n+2)==find_par(n+3)) return 0;
            if(find_par(n+4)==find_par(n+3)) return 0;
        }
        if(ed==3){
            if(find_par(n+1)==find_par(n+2)) return 0;
            if(find_par(n+1)==find_par(n+3)) return 0;
            if(find_par(n+4)==find_par(n+3)) return 0;
            if(find_par(n+4)==find_par(n+2)) return 0;
        }
        if(ed==4){
            if(find_par(n+1)==find_par(n+4)) return 0;
            if(find_par(n+2)==find_par(n+4)) return 0;
            if(find_par(n+4)==find_par(n+3)) return 0;
        }
    }
    else if(st==2){
        if(ed==3){
            if(find_par(n+1)==find_par(n+2)) return 0;
            if(find_par(n+2)==find_par(n+4)) return 0;
            if(find_par(n+2)==find_par(n+3)) return 0;
        }
        if(ed==4){
            if(find_par(n+1)==find_par(n+3)) return 0;
            if(find_par(n+2)==find_par(n+3)) return 0;
            if(find_par(n+1)==find_par(n+4)) return 0;
            if(find_par(n+4)==find_par(n+2)) return 0;
        }
    }
    else{
        if(find_par(n+1)==find_par(n+3)) return 0;
        if(find_par(n+2)==find_par(n+1)) return 0;
        if(find_par(n+4)==find_par(n+1)) return 0;
    }
    return 1;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n>>m>>w>>h;
    for(int i=1;i<=n;i++){
        ll a,b,r;
        cin>>a>>b>>r;
        arr[i]={a,b,r};
        sweep.push_back({h-b-r,1,i,n+1});
        sweep.push_back({b-r,1,i,n+3});
        sweep.push_back({w-a-r,1,i,n+2});
        sweep.push_back({a-r,1,i,n+4});
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            sweep.push_back({dist(arr[i],arr[j]),1,i,j});
        }
    }
    for(int i=1;i<=n+4;i++){
        sz[i]=1;
        par[i]=i;
    }
    for(int i=1;i<=m;i++){
        ll r,st;
        cin>>r>>st;
        sweep.push_back({2*r,0,st,i});
    }
    sort(sweep.begin(),sweep.end());
    for(auto i:sweep){
        ll type=i[1],u=i[2],v=i[3];
        if(type){
            uni(u,v);
            //cout<<u<<' '<<v<<' '<<i[0]<<ntr;
        }
        else{
            //cout<<v<<ntr;
            for(int i=1;i<=4;i++){
                if(check(u,i)) ans[v]*=10,ans[v]+=i;
            }
        }
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<ntr;
    }
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 66204 KB Output is correct
2 Correct 300 ms 66268 KB Output is correct
3 Correct 331 ms 66132 KB Output is correct
4 Correct 298 ms 66224 KB Output is correct
5 Correct 299 ms 66232 KB Output is correct
6 Correct 294 ms 66312 KB Output is correct
7 Correct 269 ms 66320 KB Output is correct
8 Correct 273 ms 66232 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6476 KB Output is correct
2 Correct 37 ms 6464 KB Output is correct
3 Correct 35 ms 6332 KB Output is correct
4 Correct 39 ms 6352 KB Output is correct
5 Correct 39 ms 6332 KB Output is correct
6 Correct 38 ms 6464 KB Output is correct
7 Correct 35 ms 5828 KB Output is correct
8 Correct 35 ms 5824 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 66204 KB Output is correct
2 Correct 300 ms 66268 KB Output is correct
3 Correct 331 ms 66132 KB Output is correct
4 Correct 298 ms 66224 KB Output is correct
5 Correct 299 ms 66232 KB Output is correct
6 Correct 294 ms 66312 KB Output is correct
7 Correct 269 ms 66320 KB Output is correct
8 Correct 273 ms 66232 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 39 ms 6476 KB Output is correct
12 Correct 37 ms 6464 KB Output is correct
13 Correct 35 ms 6332 KB Output is correct
14 Correct 39 ms 6352 KB Output is correct
15 Correct 39 ms 6332 KB Output is correct
16 Correct 38 ms 6464 KB Output is correct
17 Correct 35 ms 5828 KB Output is correct
18 Correct 35 ms 5824 KB Output is correct
19 Correct 338 ms 132916 KB Output is correct
20 Correct 335 ms 132916 KB Output is correct
21 Correct 340 ms 132980 KB Output is correct
22 Correct 328 ms 132920 KB Output is correct
23 Correct 349 ms 133036 KB Output is correct
24 Correct 340 ms 132920 KB Output is correct