oj.uz

Submission #670759

# Submission time Handle Problem Language Result Execution time Memory
670759 2022-12-10T09:40:50 Z berr Park (BOI16_park) C++17
0 / 100
 1795 ms 724 KB 
#include <bits/stdc++.h>
using namespace std;   
#define int long long 
vector<int> tx(2005), ty(2005), tr(2005), vis(2005);
int dist[4][4], x, y;
queue<int> q;
 
int check(int a, int b, int s){
    int h=(tx[a]-tx[b]);
    int e=(ty[a]-ty[b]);
    h*=h; e*=e;
 
    h+=e;
 
    int f=2*s+tr[a]+tr[b];
    
    if((f*f)>h) return 1;
    return 0;
 
}

int down(int a, int tmp){
    tmp*=2;
    if((ty[a]-tr[a])<tmp) return 1;
    return 0;
}
int up(int a, int tmp){
    tmp*=2;
    if((y-(ty[a]+tr[a]))<tmp) return 1;
    return 0;
}

int left(int a, int tmp){
    tmp*=2;
    if((tx[a]-tr[a])<tmp) return 1;
    return 0;
}


int right(int a, int tmp){
    tmp*=2;
    if((x-(tx[a]+tr[a]))<tmp) return 1;
    return 0;
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
        
 
    int n, m; cin >> n >> m;
 
     cin >> x >> y;
 
    for(int i=0; i<n; i++){
        cin>>tx[i]>>ty[i]>>tr[i];
    }
 
    int s=0;
    //l u
    for(int i=30; i>=0; i--){
        int tmp = s+(1<<i);
 
        for(int l=0; l<n; l++){
            vis[l]=0;
            if(left(l, tmp)) q.push(l), vis[l]=1;
            
        }
 
        while(q.size()){
            int v=q.front(); q.pop();
 
            for(int l=0; l<n; l++){
                if(!vis[l]&&check(l, v, tmp)){
                    vis[l]=1; q.push(l);
                }
            }
        }
 
        int flag=1;
 
        for(int l=0; l<n; l++){
            if(!vis[l]) continue;
 
            if(up(l, tmp)) flag=0;
        }
 
        if(flag) s=tmp;
    }
 
    dist[0][1]=dist[1][0]=s;
 
    s=0;
    // l, r;
    for(int i=30; i>=0; i--){
        int tmp = s+(1<<i);
 
        for(int l=0; l<n; l++){
            vis[l]=0;
            if(left(l, tmp)) q.push(l), vis[l]=1;
        }
 
        while(q.size()){
            int v=q.front(); q.pop();
 
            for(int l=0; l<n; l++){
                if(!vis[l]&&check(l, v, tmp)){
                    vis[l]=1; q.push(l);
                }
            }
        }
 
        int flag=1;
        for(int l=0; l<n; l++){
            if(!vis[l]) continue;
 
            if(right(l, tmp)) flag=0;
        }
 
        if(flag) s=tmp;
    }
    dist[0][2]=dist[2][0]=s;
 
    s=0;
    //l, d
    for(int i=30; i>=0; i--){
        int tmp = s+(1<<i);
 
        for(int l=0; l<n; l++){
            vis[l]=0;
            if(left(l, tmp)) q.push(l), vis[l]=1;
            
        }
 
        while(q.size()){
            int v=q.front(); q.pop();
 
            for(int l=0; l<n; l++){
                if(!vis[l]&&check(l, v, tmp)){
                    vis[l]=1; q.push(l);
                }
            }
        }
 
        int flag=1;
        for(int l=0; l<n; l++){
            if(!vis[l]) continue;
 
            if(down(l, tmp)) flag=0;
        }
 
        if(flag) s=tmp;
    }
    dist[0][3]=dist[3][0]=s;
 
    s=0;
    //u, r
    for(int i=30; i>=0; i--){
        int tmp = s+(1<<i);
 
        for(int l=0; l<n; l++){
            vis[l]=0;
            if((y-ty[l]-tr[l])<(tmp*2)) q.push(l), vis[l]=1;
            
        }
 
        while(q.size()){
            int v=q.front(); q.pop();
 
            for(int l=0; l<n; l++){
                if(!vis[l]&&check(l, v, tmp)){
                    vis[l]=1; q.push(l);
                }
            }
        }
 
        int flag=1;
        for(int l=0; l<n; l++){
            if(!vis[l]) continue;
 
            if(x-tx[l]-tr[l]<2*tmp) flag=0;
        }
 
        if(flag) s=tmp;
    }
 
    dist[1][2]=dist[2][1]=s;
    
    s=0;
    //u, d
    for(int i=30; i>=0; i--){
        int tmp = s+(1<<i);
 
        for(int l=0; l<n; l++){
            vis[l]=0;
            if(y-ty[l]-tr[l]<tmp*2) q.push(l), vis[l]=1;
            
        }   
 
        while(q.size()){
            int v=q.front(); q.pop();
 
            for(int l=0; l<n; l++){
                if(!vis[l]&&check(l, v, tmp)){
                    vis[l]=1;
                    q.push(l);
                }
            }
        }
 
        int flag=1;
        for(int l=0; l<n; l++){
            if(!vis[l]) continue;
 
            if(ty[l]-tr[l]<2*tmp) flag=0;
        }
        
        if(flag) s=tmp;
    }
    dist[1][3]=dist[3][1]=s;
 
    s=0;
    // r, d;
    for(int i=30; i>=0; i--){
        int tmp = s+(1<<i);
 
        for(int l=0; l<n; l++){
            vis[l]=0;
            if(x-tx[l]-tr[l]<2*tmp) q.push(l), vis[l]=1;
            
        }
 
        while(q.size()){
            int v=q.front(); q.pop();
 
            for(int l=0; l<n; l++){
                if(!vis[l]&&check(l, v, tmp)){
                    vis[l]=1; q.push(l);
                }
            }
        }
 
        int flag=1;
        for(int l=0; l<n; l++){
            if(!vis[l]) continue;
 
            if(ty[l]-tr[l]<2*tmp) flag=0;
        }
 
        if(flag) s=tmp;
    }
    dist[2][3]=dist[3][2]=s+1;
 
 
    for(int i=0; i<m; i++)
    {
        int t, s; cin>>s>>t;
        string ans;
        if(t==1){
            ans+='1';
            if(min({dist[0][3], dist[1][3], dist[2][3]})>=s) ans+='2';
            if(min({dist[0][2], dist[0][3], dist[1][3], dist[1][2]})>=s) ans+='3';
            if(min({dist[0][3], dist[0][2], dist[0][1]})>=s) ans+='4';
 
        }
 
        if(t==2){
            if(min({dist[0][3], dist[1][3], dist[2][3]})>=s) ans+='1';
            ans+='2';
            if(min({dist[2][1], dist[2][3], dist[2][0]})>=s) ans+='3';
            if(min({dist[0][1], dist[0][2], dist[1][3], dist[2][3]})>=s) ans+='4';
 
        }
        if(t==3){
            if(min({dist[0][2], dist[0][3], dist[1][3], dist[1][2]})>=s) ans+='1';
            if(min({dist[2][1], dist[2][3], dist[2][0]})>=s) ans+='2';
            ans+='3';
            if(min({dist[1][3], dist[1][2], dist[1][0]})>=s) ans+='4';
 
        }
        if(t==4){
            if(min({dist[0][3], dist[0][2], dist[0][1]})>=s) ans+='1';
            if(min({dist[0][1], dist[0][2], dist[1][3], dist[2][3]})>=s) ans+='2';
            if(min({dist[1][3], dist[1][2], dist[1][0]})>=s) ans+='3';
            ans+='4';
        }
 
        cout<<ans<<"\n";
 
    }
 
 
 
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1775 ms 380 KB Output is correct
2 Correct 1704 ms 384 KB Output is correct
3 Correct 1345 ms 460 KB Output is correct
4 Correct 1496 ms 376 KB Output is correct
5 Correct 1524 ms 388 KB Output is correct
6 Correct 1254 ms 340 KB Output is correct
7 Correct 1719 ms 380 KB Output is correct
8 Correct 1795 ms 376 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 628 KB Output is correct
2 Correct 36 ms 628 KB Output is correct
3 Correct 39 ms 600 KB Output is correct
4 Correct 38 ms 724 KB Output is correct
5 Incorrect 36 ms 628 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1775 ms 380 KB Output is correct
2 Correct 1704 ms 384 KB Output is correct
3 Correct 1345 ms 460 KB Output is correct
4 Correct 1496 ms 376 KB Output is correct
5 Correct 1524 ms 388 KB Output is correct
6 Correct 1254 ms 340 KB Output is correct
7 Correct 1719 ms 380 KB Output is correct
8 Correct 1795 ms 376 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -