oj.uz

Submission #1104732

# Submission time Handle Problem Language Result Execution time Memory
1104732 2024-10-24T09:38:30 Z ShadowShark Park (BOI16_park) C++17
100 / 100
 394 ms 86968 KB 
#include <bits/stdc++.h>
using namespace std;
///  4
/// 1 3
///  2

const int maxN = 1e5 + 5;
int x[maxN], y[maxN], w[maxN], Qw[maxN], Qe[maxN], res[maxN], check[5][5], did[5][5];
int par[2010], sz[2010];
pair<int, int> save[4000005];
vector<pair<int, double>> event;

bool cmp (pair<int, double> A, pair<int, double> B) {
    if (A.second != B.second) return A.second < B.second;
    return A.first < B.first;
}

double cal_dis(int i, int j) {
    double len = 1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]); len = sqrt(len);
    return len - w[i] - w[j];
}

int find_set(int u) {
    return (u == par[u]) ? u : par[u] = find_set(par[u]);
}

void union_set(int u, int v) {
    u = find_set(u);
    v = find_set(v);

    if (u == v) return ;

    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
}

void update_state(int n) {
    /// 1 -> 2
    if (!did[1][2] && find_set(n + 1) == find_set(n + 2)) {
        check[1][2] = check[1][3] = check[1][4] = 0;
        check[2][1] = check[3][1] = check[4][1] = 0;
        did[1][2] = 1;
    }

    if (!did[2][3] && find_set(n + 2) == find_set(n + 3)) {
        check[2][1] = check[2][3] = check[2][4] = 0;
        check[1][2] = check[3][2] = check[4][2] = 0;
        did[2][3] = 1;
    }

    if (!did[3][4] && find_set(n + 3) == find_set(n + 4)) {
        check[3][1] = check[3][2] = check[3][4] = 0;
        check[1][3] = check[2][3] = check[4][3] = 0;
        did[3][4] = 1;
    }

    if (!did[4][1] && find_set(n + 4) == find_set(n + 1)) {
        check[4][1] = check[4][2] = check[4][3] = 0;
        check[1][4] = check[2][4] = check[3][4] = 0;
        did[4][1] = 1;
    }

    if (!did[1][3] && find_set(n + 1) == find_set(n + 3)) {
        check[1][4] = check[1][3] = check[2][4] = check[2][3] = 0;
        check[4][1] = check[3][1] = check[4][2] = check[3][2] = 0;
        did[1][3] = 1;
    }

    if (!did[2][4] && find_set(n + 2) == find_set(n + 4)) {
        check[1][2] = check[1][3] = check[4][2] = check[4][3] = 0;
        check[2][1] = check[3][1] = check[2][4] = check[3][4] = 0;
        did[2][4] = 1;
    }
}

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

    int n, q, X, Y, m = 0;
    cin >> n >> q >> X >> Y;

    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            event.push_back({++m, cal_dis(i, j)});
            save[m] = {i, j};
        }
        event.push_back({++m, (x[i] - w[i])}); save[m] = {i, n + 1};
        event.push_back({++m, (y[i] - w[i])}); save[m] = {i, n + 2};
        event.push_back({++m, (X - x[i] - w[i])}); save[m] = {i, n + 3};
        event.push_back({++m, (Y - y[i] - w[i])}); save[m] = {i, n + 4};
    }

    for (int i = 1; i <= q; i++) {
        cin >> Qw[i] >> Qe[i];
        event.push_back({-i, 2 * Qw[i]});
    }

    for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++)
            check[i][j] = j;

    sort(event.begin(), event.end(), cmp);

    for (int i = 1; i <= n + 4; i++) {
        par[i] = i;
        sz[i] = 1;
    }

    for (auto it: event) {
        int id = it.first;
        if (id > 0) {
            auto [u, v] = save[id];
            union_set(u, v);
        }
        else {
            id = abs(id);
            update_state(n);
            int ans = 0;
            for (int i = 1; i <= 4; i++)
                if (check[Qe[id]][i]) ans = ans * 10 + check[Qe[id]][i];
            res[id] = ans;
        }
    }

    for (int i = 1; i <= q; i++)
        cout << res[i] << '\n';
    return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 51896 KB Output is correct
2 Correct 335 ms 51876 KB Output is correct
3 Correct 345 ms 52008 KB Output is correct
4 Correct 335 ms 52024 KB Output is correct
5 Correct 350 ms 51888 KB Output is correct
6 Correct 348 ms 52032 KB Output is correct
7 Correct 307 ms 52084 KB Output is correct
8 Correct 323 ms 51888 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5836 KB Output is correct
2 Correct 34 ms 5836 KB Output is correct
3 Correct 34 ms 5836 KB Output is correct
4 Correct 33 ms 5836 KB Output is correct
5 Correct 35 ms 5836 KB Output is correct
6 Correct 42 ms 5836 KB Output is correct
7 Correct 32 ms 5580 KB Output is correct
8 Correct 32 ms 5580 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 51896 KB Output is correct
2 Correct 335 ms 51876 KB Output is correct
3 Correct 345 ms 52008 KB Output is correct
4 Correct 335 ms 52024 KB Output is correct
5 Correct 350 ms 51888 KB Output is correct
6 Correct 348 ms 52032 KB Output is correct
7 Correct 307 ms 52084 KB Output is correct
8 Correct 323 ms 51888 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 35 ms 5836 KB Output is correct
12 Correct 34 ms 5836 KB Output is correct
13 Correct 34 ms 5836 KB Output is correct
14 Correct 33 ms 5836 KB Output is correct
15 Correct 35 ms 5836 KB Output is correct
16 Correct 42 ms 5836 KB Output is correct
17 Correct 32 ms 5580 KB Output is correct
18 Correct 32 ms 5580 KB Output is correct
19 Correct 393 ms 86968 KB Output is correct
20 Correct 394 ms 86856 KB Output is correct
21 Correct 363 ms 86956 KB Output is correct
22 Correct 367 ms 86940 KB Output is correct
23 Correct 381 ms 86948 KB Output is correct
24 Correct 347 ms 86904 KB Output is correct