oj.uz

Submission #714892

# Submission time Handle Problem Language Result Execution time Memory
714892 2023-03-25T11:53:35 Z Stickfish Park (BOI16_park) C++17
27 / 100
 2500 ms 33396 KB 
#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;

struct point {
    ll x;
    ll y;

    point() {}

    point(ll x_, ll y_): x(x_), y(y_) {}

    point operator-(const point pt) const {
        return {x - pt.x, y - pt.y};
    }

    ll sqlen() {
        return x * x + y * y;
    }
};

struct circle {
    point center;
    ll r;
};

struct dsu {
    void resize(int n) {
        rt.resize(n);
        sz.assign(n, 1);
        for (int i = 0; i < n; ++i)
            rt[i] = i;
    }

    int gst(int i) {
        if (rt[i] == i)
            return i;
        return rt[i] = gst(rt[i]);
    }

    void unite(int i, int j) {
        i = gst(i);
        j = gst(j);
        if (i == j)
            return;
        if (sz[i] < sz[j])
            swap(i, j);
        rt[j] = i;
        sz[i] += sz[j];
    }

    int size() {
        return rt.size();
    }
 private:
     vector<int> rt;
     vector<int> sz;
};

const int MAXN = 2001;
circle t[MAXN];

dsu get_dsu(int n, vector<pair<ll, pair<int, int>>>& edges, ll w) {
    dsu su;
    su.resize(n);
    for (auto p : edges) {
        if (p.first <= w) {
            su.unite(p.second.first, p.second.second);
        }
    }
    return su;
}

signed main() {
    int n, m;
    cin >> n >> m;
    ll w, h;
    cin >> w >> h;
    for (int i = 0; i < n; ++i) {
        cin >> t[i].center.x >> t[i].center.y >> t[i].r;
    }
    vector<pair<ll, pair<int, int>>> edges;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            // r[i] + r[j] + w >= dist(i, j)
            ll w = sqrtl((t[i].center - t[j].center).sqlen()) - t[i].r - t[j].r + 1;
            edges.push_back({w, {i, j}});
        }
        edges.push_back({t[i].center.x - t[i].r + 1, {i, n}});
        edges.push_back({t[i].center.y - t[i].r + 1, {i, n + 1}});
        edges.push_back({w - t[i].center.x - t[i].r + 1, {i, n + 2}});
        edges.push_back({h - t[i].center.y - t[i].r + 1, {i, n + 3}});
    }
    sort(edges.begin(), edges.end());
    //for (auto [w, e] : edges) {
        //cout << w << ": " << e.first + 1 << ' ' << (e.second < n ? e.second + 1 : n - e.second - 1) << endl;
    //}
    vector<pair<ll, int>> vis(m);
    for (int i = 0; i < m; ++i) {
        cin >> vis[i].first >> vis[i].second;
        vis[i].first *= 2;
    }
    //for (int i = 0; i < 6; ++i) {
        //cout << visr[wblock[i]] << ' ';
    //}
    //cout << endl;
    for (auto [r, c] : vis) {
        --c;
        bitset<6> blocks;
        dsu su = get_dsu(n + 4, edges, r);
        blocks[0] = su.gst(n) == su.gst(n + 1);
        blocks[1] = su.gst(n + 1) == su.gst(n + 2);
        blocks[2] = su.gst(n + 2) == su.gst(n + 3);
        blocks[3] = su.gst(n + 3) == su.gst(n);
        blocks[4] = su.gst(n) == su.gst(n + 2);
        blocks[5] = su.gst(n + 1) == su.gst(n + 3);
        bitset<4> ans;
        ans[c] = 1;
        for (int e = 0; e < 4; ++e) {
            if (blocks[e] || blocks[c])
                continue;
            if (((e ^ c) & 2) && blocks[4])
                continue;
            if ((__builtin_popcount(e) + __builtin_popcount(c)) % 2 && blocks[5])
                continue;
            ans[e] = 1;
        }
        for (int e = 0; e < 4; ++e) {
            if (ans[e])
                cout << e + 1;
        }
        cout << '\n';
    }
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 33268 KB Output is correct
2 Correct 269 ms 33320 KB Output is correct
3 Correct 278 ms 33256 KB Output is correct
4 Correct 344 ms 33268 KB Output is correct
5 Correct 269 ms 33312 KB Output is correct
6 Correct 287 ms 33288 KB Output is correct
7 Correct 270 ms 33396 KB Output is correct
8 Correct 271 ms 33312 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1545 ms 3032 KB Output is correct
2 Correct 1227 ms 2980 KB Output is correct
3 Correct 1433 ms 3044 KB Output is correct
4 Correct 1139 ms 3304 KB Output is correct
5 Correct 1167 ms 3144 KB Output is correct
6 Execution timed out 2528 ms 3108 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 33268 KB Output is correct
2 Correct 269 ms 33320 KB Output is correct
3 Correct 278 ms 33256 KB Output is correct
4 Correct 344 ms 33268 KB Output is correct
5 Correct 269 ms 33312 KB Output is correct
6 Correct 287 ms 33288 KB Output is correct
7 Correct 270 ms 33396 KB Output is correct
8 Correct 271 ms 33312 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1545 ms 3032 KB Output is correct
12 Correct 1227 ms 2980 KB Output is correct
13 Correct 1433 ms 3044 KB Output is correct
14 Correct 1139 ms 3304 KB Output is correct
15 Correct 1167 ms 3144 KB Output is correct
16 Execution timed out 2528 ms 3108 KB Time limit exceeded
17 Halted 0 ms 0 KB -