oj.uz

Submission #374447

# Submission time Handle Problem Language Result Execution time Memory
374447 2021-03-07T09:56:30 Z Mahdi_Shokoufi Park (BOI16_park) C++17
100 / 100
 412 ms 58600 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()

typedef long long ll;

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

ll x[N], y[N], r[N], par[N], sz[N], ans[M][5];
vector < pair < double , pair < ll , ll > > > 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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 49852 KB Output is correct
2 Correct 337 ms 50032 KB Output is correct
3 Correct 341 ms 49852 KB Output is correct
4 Correct 344 ms 49852 KB Output is correct
5 Correct 338 ms 49864 KB Output is correct
6 Correct 351 ms 49828 KB Output is correct
7 Correct 329 ms 49852 KB Output is correct
8 Correct 312 ms 49828 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8668 KB Output is correct
2 Correct 67 ms 8668 KB Output is correct
3 Correct 63 ms 8668 KB Output is correct
4 Correct 64 ms 8668 KB Output is correct
5 Correct 65 ms 8668 KB Output is correct
6 Correct 65 ms 8796 KB Output is correct
7 Correct 59 ms 8288 KB Output is correct
8 Correct 59 ms 8288 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 49852 KB Output is correct
2 Correct 337 ms 50032 KB Output is correct
3 Correct 341 ms 49852 KB Output is correct
4 Correct 344 ms 49852 KB Output is correct
5 Correct 338 ms 49864 KB Output is correct
6 Correct 351 ms 49828 KB Output is correct
7 Correct 329 ms 49852 KB Output is correct
8 Correct 312 ms 49828 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 68 ms 8668 KB Output is correct
12 Correct 67 ms 8668 KB Output is correct
13 Correct 63 ms 8668 KB Output is correct
14 Correct 64 ms 8668 KB Output is correct
15 Correct 65 ms 8668 KB Output is correct
16 Correct 65 ms 8796 KB Output is correct
17 Correct 59 ms 8288 KB Output is correct
18 Correct 59 ms 8288 KB Output is correct
19 Correct 409 ms 58352 KB Output is correct
20 Correct 406 ms 58384 KB Output is correct
21 Correct 412 ms 58600 KB Output is correct
22 Correct 402 ms 58508 KB Output is correct
23 Correct 403 ms 58224 KB Output is correct
24 Correct 388 ms 58480 KB Output is correct