oj.uz

Submission #764795

# Submission time Handle Problem Language Result Execution time Memory
764795 2023-06-24T04:37:29 Z joshuaZ Park (BOI16_park) C++17
100 / 100
 411 ms 71000 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int mxN = 2005;

int n, m; ll w, h;

struct tree {
    ll r, x, y;
};

struct edge {
    long double w;
    int u, v;
};

struct query {
    long double r;
    int id, ent;
};

int p[mxN], sz[mxN];

int fd(int u){
    return p[u] == u ? u : p[u] = fd(p[u]);
}

void unite(int u, int v){
    int x = fd(u), y = fd(v);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    sz[x] += sz[y];
    p[y] = x;
}

bool same(int u, int v){
    return fd(u) == fd(v);
}

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

    for (int i = 0; i < mxN; i++){
        p[i] = i;
        sz[i] = 1;
    }

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

    vector<tree> t;
    for (int i = 0, x, y, r; i < n; i++){
        cin >> x >> y >> r;
        t.push_back({r, x, y});
    }

    vector<edge> e;
    for (int i = 0; i < n; i++){
        e.push_back({(long double)t[i].y - t[i].r, i, n + 1}); //bottom
        e.push_back({(long double)w - t[i].x - t[i].r, i, n + 2}); //right
        e.push_back({(long double)h - t[i].y - t[i].r, i, n + 3}); //top
        e.push_back({(long double)t[i].x - t[i].r, i, n + 4}); //left
    }

    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            long double d = sqrtl(abs(t[i].x - t[j].x) * abs(t[i].x - t[j].x) + abs(t[i].y - t[j].y) * abs(t[i].y - t[j].y));
            e.push_back({d - (t[i].r + t[j].r), i, j});
        }
    }

    e.push_back({1e12, 0, 0});

    sort(e.begin(), e.end(), [](edge p, edge q){ return p.w < q.w; });

    vector<query> queries(m);
    for (int i = 0; i < m; i++){
        queries[i].id = i;
        cin >> queries[i].r >> queries[i].ent;
    }

    sort(queries.begin(), queries.end(), [](query x, query y){ return x.r < y.r; });

    int pos = 0;
    vector<string> a(m);
    for (auto &q : queries){
        while (2.0 * q.r - e[pos].w > 1e-10){
            unite(e[pos].u, e[pos].v);
            pos++;
        }
        string s;
        bool c1 = same(n+4,n+1), c2 = same(n+1, n+2), c3 = same(n+2, n+3), c4 = same(n+3, n+4);
        bool hori = same(n+2, n+4), vert = same(n+1, n+3);
        if (q.ent == 1){
            s += "1";
            if (!(c1 || c2 || vert)) s += "2";
            if (!(c1 || c3 || hori || vert)) s += "3";
            if (!(c1 || c4 || hori)) s += "4";
        } else if (q.ent == 2){
            if (!(c1 || c2 || vert)) s += "1";
            s += "2";
            if (!(c2 || c3 || hori)) s += "3";
            if (!(c2 || c4 || vert || hori)) s += "4";
        } else if (q.ent == 3){
            if (!(c1 || c3 || hori || vert)) s += "1";
            if (!(c2 || c3 || hori)) s += "2";
            s += "3";
            if (!(c3 || c4 || vert)) s += "4";
        } else {
            if (!(c1 || c4 || hori)) s += "1";
            if (!(c2 || c4 || vert || hori)) s += "2";
            if (!(c3 || c4 || vert)) s += "3";
            s += "4";
        }
        a[q.id] = s;
    }

    for (int i = 0; i < m; i++){
        cout << a[i] << '\n';
    }
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 66124 KB Output is correct
2 Correct 345 ms 66196 KB Output is correct
3 Correct 381 ms 66268 KB Output is correct
4 Correct 352 ms 66232 KB Output is correct
5 Correct 353 ms 66256 KB Output is correct
6 Correct 345 ms 66212 KB Output is correct
7 Correct 334 ms 66248 KB Output is correct
8 Correct 327 ms 66160 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7656 KB Output is correct
2 Correct 48 ms 8780 KB Output is correct
3 Correct 63 ms 8724 KB Output is correct
4 Correct 49 ms 8784 KB Output is correct
5 Correct 48 ms 8792 KB Output is correct
6 Correct 48 ms 8728 KB Output is correct
7 Correct 52 ms 7988 KB Output is correct
8 Correct 44 ms 8012 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 66124 KB Output is correct
2 Correct 345 ms 66196 KB Output is correct
3 Correct 381 ms 66268 KB Output is correct
4 Correct 352 ms 66232 KB Output is correct
5 Correct 353 ms 66256 KB Output is correct
6 Correct 345 ms 66212 KB Output is correct
7 Correct 334 ms 66248 KB Output is correct
8 Correct 327 ms 66160 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 47 ms 7656 KB Output is correct
12 Correct 48 ms 8780 KB Output is correct
13 Correct 63 ms 8724 KB Output is correct
14 Correct 49 ms 8784 KB Output is correct
15 Correct 48 ms 8792 KB Output is correct
16 Correct 48 ms 8728 KB Output is correct
17 Correct 52 ms 7988 KB Output is correct
18 Correct 44 ms 8012 KB Output is correct
19 Correct 388 ms 70904 KB Output is correct
20 Correct 398 ms 70904 KB Output is correct
21 Correct 395 ms 70904 KB Output is correct
22 Correct 401 ms 70768 KB Output is correct
23 Correct 411 ms 70916 KB Output is correct
24 Correct 378 ms 71000 KB Output is correct