Submission #477939

#	Time	Username	Problem	Language	Result	Execution time	Memory
477939		Lobo	Park (BOI16_park)	C++17	100 / 100	1649 ms	202260 KiB

park

#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 2200

dbl w,h;
ll n, m, ds[maxn];
string ans[110000];

ii find(ii u) {
    if(u == ds[u]) return u;

    return ds[u] = find(ds[u]);
}

void join(ii u, ii v) {
    ds[v] = u;
}

bool alone(ii x) {
    if(x == 1) return find(3) == find(4);
    else if(x == 2) return find(2) == find(3);
    else if(x == 3) return find(1) == find(2);
    else return find(4) == find(1);
}

bool ver() {
    return find(1) != find(3);
}

bool hor() {
    return find(2) != find(4);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);

    cin >> n >> m;
    cin >> w >> h;

    for(ii i = 1; i <= n+10; i++) {
        ds[i] = i;
    }

    priority_queue<pair<pair<dbl,ll>,pair<ll,ll>>, vector<pair<pair<dbl,ll>,pair<ll,ll>>>, greater<pair<pair<dbl,ll>,pair<ll,ll>>>> pq;

    vector<pair<dbl,pair<dbl,dbl>>> tree;
    for(ii i = 0; i < n; i++) {
        dbl x,y,r;
        cin >> x >> y >> r;
        tree.pb(mp(r,mp(x,y)));
    }

    for(ii i = 0; i < n; i++) {
        dbl x1 = tree[i].sc.fr;
        dbl y1 = tree[i].sc.sc;
        dbl r1 = tree[i].fr;

        pq.push(mp(mp(abs(h-y1-r1),1),mp(1,i+5)));
        pq.push(mp(mp(abs(w-x1-r1),1),mp(2,i+5)));
        pq.push(mp(mp(abs(y1-r1),1),mp(3,i+5)));
        pq.push(mp(mp(abs(x1-r1),1),mp(4,i+5)));

        for(ii j = i+1; j < n; j++) {
            dbl x2 = tree[j].sc.fr;
            dbl y2 = tree[j].sc.sc;
            dbl r2 = tree[j].fr;

            //cout << i+5 << " " << j+5 << " = " << sqrt(pow(x1-x2,2.0)+pow(y1-y2,2.0))-r1-r2 << endl;
            pq.push(mp(mp(sqrt(pow(x1-x2,2.0)+pow(y1-y2,2.0))-r1-r2,1),mp(i+5,j+5)));
        }
    }

    for(ii i = 0; i < m; i++) {
        dbl r;
        ll e;
        cin >> r >> e;

        pq.push(mp(mp(2*r,-i),mp(e,e)));
    }

    while(pq.size()) {
        if(pq.top().fr.sc == 1) {
            ll u = pq.top().sc.fr;
            ll v = pq.top().sc.sc;
            pq.pop();

            //cout << u << " com " << v << endl;
            u = find(u);
            v = find(v);
            //cout << " " << u << " - " << v << endl << endl;

            if(u != v) join(u,v);
        }
        else {
            ll id = -pq.top().fr.sc;
            ll e = pq.top().sc.fr;
            pq.pop();

            //cout << id << " " << e << endl;
            //cout << " 1 " << " " << find(1) << endl;
            //cout << " 2 " << " " << find(2) << endl;
            //cout << " 3 " << " " << find(3) << endl;
            //cout << " 4 " << " " << find(4) << endl;

            if(e == 1) {
                ans[id]+= '1';
                if(alone(e)) continue;
                if(ver() && !alone(2)) ans[id]+= '2';
                if(hor() && ver() && !alone(3)) ans[id]+= '3';
                if(hor() && !alone(4)) ans[id]+= '4';

                

            }
            else if(e == 2) {
                ans[id]+= '2';
                if(alone(e)) continue;
                if(ver() && !alone(1)) ans[id]+= '1';
                if(hor() && ver() && !alone(4)) ans[id]+= '4';
                if(hor() && !alone(3)) ans[id]+= '3';

            }
            else if(e == 3) {
                ans[id]+= '3';
                if(alone(e)) continue;
                if(ver() && !alone(4)) ans[id]+= '4';
                if(hor() && ver() && !alone(1)) ans[id]+= '1';
                if(hor() && !alone(2)) ans[id]+= '2';
            }
            else {
                ans[id]+= '4';
                if(alone(e)) continue;
                if(ver() && !alone(3)) ans[id]+= '3';
                if(hor() && ver() && !alone(2)) ans[id]+= '2';
                if(hor() && !alone(1)) ans[id]+= '1';
            }

            sort(all(ans[id]));

        }

    }

    for(ii i = 0; i < m; i++) {
        cout << ans[i] << endl;
    }





}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42