oj.uz

Submission #950304

# Submission time Handle Problem Language Result Execution time Memory
950304 2024-03-20T07:52:41 Z LittleOrange Park (BOI16_park) C++17
100 / 100
 530 ms 56420 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
    ll x,y,r;
};
ll dis(const obj &a, const obj &b){
    ll d2 = (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    ll d = a.r+b.r;
    if (d2<=d*d) return 0;
    ll l = 0,r=1e9;
    while(l<r){
        ll m = l+r+1>>1;
        if (d2<(d+m)*(d+m)){
            r = m-1;
        }else{
            l = m;
        }
    }
    return l;
}
struct query{
    ll r,e,i;
    bool operator<(const query &o) const{
        return r<o.r;
    }
};
struct dsu{
    ll n;
    vector<ll> p;
    dsu(ll N):n(N),p(N,-1){}
    ll g(ll i){
        return p[i]==-1?i : p[i] = g(p[i]);
    }
    void m(ll a, ll b){
        a = g(a);
        b = g(b);
        if (a!=b) p[a] = b;
    }
    bool e(ll a, ll b){
        return g(a)==g(b);
    }
};
struct op{
    ll i,j,r;
    bool operator<(const op &o) const{
        return r>o.r;
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,m,w,h;
    cin >> n >> m >> w >> h;
    vector<obj> a(n);
    for(obj &o : a) cin >> o.x >> o.y >> o.r;
    vector<op> b;
    for(ll i = 0;i<n;i++){
        obj o = a[i];
        b.push_back({0,i+4,h-o.y-o.r});
        b.push_back({1,i+4,o.x-o.r});
        b.push_back({2,i+4,o.y-o.r});
        b.push_back({3,i+4,w-o.x-o.r});
        for(ll j = i+1;j<n;j++){
            obj v = a[j];
            b.push_back({i+4,j+4,dis(o,v)});
        }
    }
    dsu d(n+10);
/*
4   3
 
1   2
 
 0
1 3
 2
 
*/
    auto check = [&](ll a, ll b){
        if (a==b) return true;
        if (a>b) swap(a,b);
        if (a==1){
            if (b == 2) return !(d.e(2,0)||d.e(2,1)||d.e(2,3));
            else if (b==3) return !(d.e(1,2)||d.e(0,3)||d.e(0,2)||d.e(1,3));
            else return !(d.e(1,0)||d.e(1,2)||d.e(1,3));
        }else if (a==2){
            if (b==3) return !(d.e(3,0)||d.e(3,1)||d.e(3,2));
            else return !(d.e(0,1)||d.e(2,3)||d.e(0,2)||d.e(1,3));
        }else{
            return !(d.e(0,1)||d.e(0,2)||d.e(0,3));
        }
    };
    sort(b.begin(),b.end());
    while(b.size()&&b.back().r<=0){
        auto [i,j,r] = b.back();b.pop_back();
        d.m(i,j);
    }
    vector<query> qs(m);
    for(ll i = 0;i<m;i++){
        cin >> qs[i].r >> qs[i].e;
        qs[i].i = i;
    }
    sort(qs.begin(),qs.end());
    vector<string> ans(m);
    for(auto [r,e,i] : qs){
        while(b.size()&&b.back().r<r*2){
            auto [i,j,r] = b.back();b.pop_back();
            d.m(i,j);
        }
        /*
        cout << "query " << i+1 << "\n";
        for(ll i = 0;i<4;i++){
            for(ll j = 0;j<4;j++){
                cout << d.e(i,j) << " \n"[j==3];
            }
        }
        */
        for(ll z = 1;z<=4;z++){
            if (check(z,e)) ans[i].push_back((char)(z+'0'));
        }
    }
    for(auto &o : ans) cout << o << "\n";
}

Compilation message

park.cpp: In function 'll dis(const obj&, const obj&)':
park.cpp:13:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |         ll m = l+r+1>>1;
      |                ~~~^~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 51680 KB Output is correct
2 Correct 507 ms 50504 KB Output is correct
3 Correct 488 ms 51424 KB Output is correct
4 Correct 490 ms 50516 KB Output is correct
5 Correct 500 ms 51464 KB Output is correct
6 Correct 488 ms 50856 KB Output is correct
7 Correct 448 ms 50600 KB Output is correct
8 Correct 439 ms 50852 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7816 KB Output is correct
2 Correct 34 ms 7824 KB Output is correct
3 Correct 33 ms 7884 KB Output is correct
4 Correct 33 ms 7884 KB Output is correct
5 Correct 33 ms 7928 KB Output is correct
6 Correct 34 ms 7892 KB Output is correct
7 Correct 27 ms 7400 KB Output is correct
8 Correct 27 ms 7252 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 51680 KB Output is correct
2 Correct 507 ms 50504 KB Output is correct
3 Correct 488 ms 51424 KB Output is correct
4 Correct 490 ms 50516 KB Output is correct
5 Correct 500 ms 51464 KB Output is correct
6 Correct 488 ms 50856 KB Output is correct
7 Correct 448 ms 50600 KB Output is correct
8 Correct 439 ms 50852 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 36 ms 7816 KB Output is correct
12 Correct 34 ms 7824 KB Output is correct
13 Correct 33 ms 7884 KB Output is correct
14 Correct 33 ms 7884 KB Output is correct
15 Correct 33 ms 7928 KB Output is correct
16 Correct 34 ms 7892 KB Output is correct
17 Correct 27 ms 7400 KB Output is correct
18 Correct 27 ms 7252 KB Output is correct
19 Correct 525 ms 55232 KB Output is correct
20 Correct 530 ms 54680 KB Output is correct
21 Correct 515 ms 54872 KB Output is correct
22 Correct 519 ms 55420 KB Output is correct
23 Correct 522 ms 55196 KB Output is correct
24 Correct 496 ms 56420 KB Output is correct