Submission #950304

#	Time	Username	Problem	Language	Result	Execution time	Memory
950304		LittleOrange	Park (BOI16_park)	C++17	100 / 100	530 ms	56420 KiB

park

#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 (stderr)

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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42