Submission #374452

#	Time	Username	Problem	Language	Result	Execution time	Memory
374452		Mahdi_Shokoufi	Park (BOI16_park)	C++17	100 / 100	413 ms	37852 KiB

park

//In the name of Allah
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define Sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()

const int N = 2010;
const int M = 1e5 + 10;

int x[N], y[N], r[N], par[N], sz[N], ans[M][5];
vector < pair < double , pair < int , int > > > vec, qry;

int getPar(int v){
    return par[v] == v ? v : par[v] = getPar(par[v]);
}

void merge(int u, int v){
    u = getPar(u); v = getPar(v);
    if (u == v)
        return;
    if (sz[v] < sz[u])
        swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
}

bool c(int u, int v){
    return getPar(u) != getPar(v);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q, w, h;
    cin >> n >> q >> w >> h;
    n += 4;
    for (int i = 5; i <= n; i ++)
        cin >> x[i] >> y[i] >> r[i];
    for (int i = 5; i <= n; i ++){
        vec.pb(mp(x[i] - r[i], mp(1, i)));
        vec.pb(mp(y[i] - r[i], mp(2, i)));
        vec.pb(mp(w - x[i] - r[i], mp(3, i)));
        vec.pb(mp(h - y[i] - r[i], mp(4, i)));
        for (int j = i + 1; j <= n; j ++)
            vec.pb(mp(sqrt(1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]) + 0.0) - r[i] - r[j], mp(i, j)));
    }
    for (int i = 0; i < q; i ++){
        int rd, p; cin >> rd >> p;
        qry.pb(mp(2 * rd, mp(p, i)));
    }
    sort(all(vec)); sort(all(qry));
    int ptr = 0;
    for (int i = 0; i < N; i ++)
        par[i] = i, sz[i] = 1;
    for (int i = 0; i < q; i ++){
        while (ptr < Sz(vec) && vec[ptr].X < qry[i].X)
            merge(vec[ptr].Y.X, vec[ptr].Y.Y), ptr ++;
        int p = qry[i].Y.X, id = qry[i].Y.Y;
        ans[id][p] = 1;
        if (p == 1){
            ans[id][2] = c(2, 1) && c(2, 3) && c(2, 4);
            ans[id][3] = c(1, 2) && c(1, 3) && c(2, 4) && c(3, 4);
            ans[id][4] = c(1, 2) && c(1, 3) && c(1, 4);
        }
        else if (p == 2){
            ans[id][1] = c(2, 1) && c(2, 3) && c(2, 4);
            ans[id][3] = c(3, 1) && c(3, 2) && c(3, 4);
            ans[id][4] = c(1, 3) && c(1, 4) && c(2, 3) && c(2, 4);
        }
        else if (p == 3){
            ans[id][1] = c(1, 2) && c(1, 3) && c(2, 4) && c(3, 4);
            ans[id][2] = c(3, 1) && c(3, 2) && c(3, 4);
            ans[id][4] = c(4, 1) && c(4, 2) && c(4, 3);
        }
        else{
            ans[id][1] = c(1, 2) && c(1, 3) && c(1, 4);
            ans[id][2] = c(1, 3) && c(1, 4) && c(2, 3) && c(2, 4);
            ans[id][3] = c(4, 1) && c(4, 2) && c(4, 3);
        }
    }
    for (int i = 0; i < q; i ++){
        for (int j = 1; j <= 4; j ++)
            if (ans[i][j])
                cout << j;
        cout << '\n';
    }
    return 0;
}

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