oj.uz

Submission #1098568

# Submission time Handle Problem Language Result Execution time Memory
1098568 2024-10-09T15:35:27 Z Bananabread Park (BOI16_park) C++17
27 / 100
 311 ms 66380 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+3)) 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 292 ms 66208 KB Output is correct
2 Correct 297 ms 66204 KB Output is correct
3 Correct 311 ms 66380 KB Output is correct
4 Correct 302 ms 66216 KB Output is correct
5 Correct 303 ms 66204 KB Output is correct
6 Correct 305 ms 66172 KB Output is correct
7 Correct 287 ms 66204 KB Output is correct
8 Correct 278 ms 66204 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6444 KB Output is correct
2 Incorrect 38 ms 6344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 66208 KB Output is correct
2 Correct 297 ms 66204 KB Output is correct
3 Correct 311 ms 66380 KB Output is correct
4 Correct 302 ms 66216 KB Output is correct
5 Correct 303 ms 66204 KB Output is correct
6 Correct 305 ms 66172 KB Output is correct
7 Correct 287 ms 66204 KB Output is correct
8 Correct 278 ms 66204 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 39 ms 6444 KB Output is correct
12 Incorrect 38 ms 6344 KB Output isn't correct
13 Halted 0 ms 0 KB -