oj.uz

Submission #535623

# Submission time Handle Problem Language Result Execution time Memory
535623 2022-03-10T16:57:48 Z __Variatto Park (BOI16_park) C++17
31 / 100
 2500 ms 644 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e3+10;
int fau[MAX];
int Find(int a){
    if(fau[a]==a)
        return a;
    return fau[a]=Find(fau[a]);
}
void Union(int a, int b){
    fau[Find(a)]=fau[Find(b)];
}
int n, m, w, h;
ll x[MAX], y[MAX], r[MAX];
bool spr(int e1, int e2, int pro){
    for(int i=1; i<=n+4; i++)
        fau[i]=i;
    for(int i=1; i<=n; i++){
        if(y[i]-r[i]<2*pro) Union(i, n+1);
        if(w-(x[i]+r[i])<2*pro) Union(i, n+2);
        if(h-(y[i]+r[i])<2*pro) Union(i, n+3);
        if(x[i]-r[i]<2*pro) Union(i, n+4);
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            ll odl=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            odl-=(r[i]+r[j]);
            if(odl<2*pro)
                Union(i, j);
        }
    }
    if(e1==1&&e2==2) return (Find(n+1)!=Find(n+4)&&Find(n+1)!=Find(n+2)&&Find(n+1)!=Find(n+3));
    if(e1==1&&e2==3) return(Find(n+1)!=Find(n+4)&&Find(n+4)!=Find(n+2)&&Find(n+1)!=Find(n+3)&&Find(n+2)!=Find(n+3));
    if(e1==1&&e2==4) return(Find(n+1)!=Find(n+4)&&Find(n+3)!=Find(n+4)&&Find(n+2)!=Find(n+4));
    if(e1==2&&e2==3) return (Find(n+1)!=Find(n+2)&&Find(n+3)!=Find(n+2)&&Find(n+2)!=Find(n+4));
    if(e1==2&&e2==4) return(Find(n+1)!=Find(n+3)&&Find(n+4)!=Find(n+2)&&Find(n+1)!=Find(n+2)&&Find(n+4)!=Find(n+3));
    if(e1==3&&e2==4) return (Find(n+3)!=Find(n+4)&&Find(n+3)!=Find(n+1)&&Find(n+2)!=Find(n+3));
}
int bin(int x, int y){
    int pocz=0, kon=1e9+10, sr, wyn=0;
    while(pocz<=kon){
        sr=(pocz+kon)/2;
        if(spr(x, y, sr))
            pocz=sr+1, wyn=sr;
        else
            kon=sr-1;
    }
    return wyn;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>w>>h;
    for(int i=1; i<=n; i++){
        cin>>x[i]>>y[i]>>r[i];
    }
    int maxi12=bin(1, 2), maxi13=bin(1, 3), maxi14=bin(1, 4), maxi23=bin(2, 3), maxi24=bin(2, 4), maxi34=bin(3, 4);
    while(m--){
        int pro, e;
        cin>>pro>>e;
        if(e==1){
            cout<<1;
            if(maxi12>=pro) cout<<2;
            if(maxi13>=pro) cout<<3;
            if(maxi14>=pro) cout<<4;
        }
        if(e==2){
            if(maxi12>=pro) cout<<1;
            cout<<2;
            if(maxi23>=pro) cout<<3;
            if(maxi24>=pro) cout<<4;
        }
        if(e==3){
            if(maxi13>=pro) cout<<1;
            if(maxi23>=pro) cout<<2;
            cout<<3;
            if(maxi34>=pro) cout<<4;
        }
        if(e==4){
            if(maxi14>=pro) cout<<1;
            if(maxi24>=pro) cout<<2;
            if(maxi34>=pro) cout<<3;
            cout<<4;
        }
        cout<<"\n";
    }
}

Compilation message

park.cpp: In function 'bool spr(int, int, int)':
park.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
   42 | }
      | ^

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2583 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 588 KB Output is correct
2 Correct 64 ms 632 KB Output is correct
3 Correct 62 ms 568 KB Output is correct
4 Correct 59 ms 588 KB Output is correct
5 Correct 58 ms 584 KB Output is correct
6 Correct 70 ms 644 KB Output is correct
7 Correct 29 ms 588 KB Output is correct
8 Correct 42 ms 600 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2583 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -