oj.uz

Submission #764790

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

int n, m, w, h;

struct tree {
    int 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 = sqrt(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
0 / 27.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 42.0

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