oj.uz

Submission #374175

# Submission time Handle Problem Language Result Execution time Memory
374175 2021-03-06T19:48:11 Z Mahdi_Shokoufi Park (BOI16_park) C++17
0 / 100
 328 ms 33364 KB 
//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((x[i] - x[j]) * (x[i] - x[j]) + (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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 33356 KB Output is correct
2 Incorrect 328 ms 33364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 5608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 33356 KB Output is correct
2 Incorrect 328 ms 33364 KB Output isn't correct
3 Halted 0 ms 0 KB -