oj.uz

Submission #494597

# Submission time Handle Problem Language Result Execution time Memory
494597 2021-12-15T19:54:28 Z teruel Park (BOI16_park) C++17
100 / 100
 293 ms 28664 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast","unroint-loops","omit-frame-pointer","inline","03")
#endif // ONLINE_JUDGE

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define rnk(x, y) upper_bound(all((x)), (y)) - (x).begin()

template <class T = int> using ii = pair <T, T>;
template <class T = int> using tri = tuple <T, T, T>;

typedef long double ld;
typedef long long ll;
typedef __int128 LL;


mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

static int rnd(int lo, int hi) {
    return uniform_int_distribution <int> (lo, hi)(rng);
}

const ll oo = 1e18;

const ll MAX = 1e5 + 5;
const ll mod = 1e9 + 7;

ll n, m, q, W, H, p[MAX], px[MAX], py[MAX], R[MAX];

int Get(int k) {
    return p[k] == k ? k : p[k] = Get(p[k]);
}

string sol[MAX];

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

    cin >> n >> q >> W >> H;

    vector <tri <int>> path;

    for(int i = 1; i <= n; i++) {
        ll &x = px[i], &y = py[i], &r = R[i];
        cin >> y >> x >> r;
        path.push_back(tri <ll> (H - x - r, i, n + 3));
        path.push_back(tri <ll> (W - y - r, i, n + 2));
        path.push_back(tri <ll> (x - r, i, n + 1));
        path.push_back(tri <ll> (y - r, i, n + 4));
    }

    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++) {
            ll dx = px[i] - px[j];
            ll dy = py[i] - py[j];
            int D = (int)sqrtl(dx * dx + dy * dy) - R[i] - R[j];
            path.push_back(tri <int> (D, i, j));
        }

    vector <tri <int>> v(q);

    q = 0;

    for(auto &[r, k, c] : v) {
        cin >> r >> k, c = q++, r += r;
    }

    sort(all(path));
    sort(all(v));

    for(int i = 1; i <= n + 4; i++)
        p[i] = i;

    int t = 0, a, b;
    m = path.size();

    for(auto [r, k, i] : v) {
        while(t < m) {
            auto [w, x, y] = path[t];
            if(w >= r)break;
            a = Get(x), b = Get(y);
            if(a != b)p[a] = b;
            t++;
        }

        int cut[6];

        for(int j = 1; j <= 4; j++) {
            cut[j - 1] = (Get(n + j) == Get(n + 1 + (j % 4)));
        }

        cut[4] = (Get(n + 1) == Get(n + 3));
        cut[5] = (Get(n + 2) == Get(n + 4));

        auto &s = sol[i];

        if(k == 1) {
            s += '1';
            if(!(cut[0] | cut[3] | cut[4]))s += '2';
            if(!(cut[3] | cut[1] | cut[4] | cut[5]))s += '3';
            if(!(cut[2] | cut[3] | cut[5]))s += '4';
        }
        if(k == 2) {
            if(!(cut[0] | cut[3] | cut[4]))s += '1';
            s += '2';
            if(!(cut[0] | cut[1] | cut[5]))s += '3';
            if(!(cut[0] | cut[2] | cut[4] | cut[5]))s += '4';
        }
        if(k == 3) {
            if(!(cut[3] | cut[1] | cut[4] | cut[5]))s += '1';
            if(!(cut[0] | cut[1] | cut[5]))s += '2';
            s += '3';
            if(!(cut[2] | cut[1] | cut[4]))s += '4';
        }
        if(k == 4) {
            if(!(cut[2] | cut[3] | cut[5]))s += '1';
            if(!(cut[0] | cut[2] | cut[4] | cut[5]))s += '2';
            if(!(cut[2] | cut[1] | cut[4]))s += '3';
            s += '4';
        }
    }

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

Compilation message

park.cpp:29:12: warning: 'int rnd(int, int)' defined but not used [-Wunused-function]
   29 | static int rnd(int lo, int hi) {
      |            ^~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 28212 KB Output is correct
2 Correct 232 ms 28160 KB Output is correct
3 Correct 240 ms 28212 KB Output is correct
4 Correct 237 ms 28256 KB Output is correct
5 Correct 231 ms 28212 KB Output is correct
6 Correct 253 ms 28168 KB Output is correct
7 Correct 226 ms 28192 KB Output is correct
8 Correct 204 ms 28264 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3404 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 5408 KB Output is correct
2 Correct 47 ms 5324 KB Output is correct
3 Correct 38 ms 5272 KB Output is correct
4 Correct 36 ms 5344 KB Output is correct
5 Correct 37 ms 5280 KB Output is correct
6 Correct 39 ms 5312 KB Output is correct
7 Correct 39 ms 4904 KB Output is correct
8 Correct 59 ms 4932 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 28212 KB Output is correct
2 Correct 232 ms 28160 KB Output is correct
3 Correct 240 ms 28212 KB Output is correct
4 Correct 237 ms 28256 KB Output is correct
5 Correct 231 ms 28212 KB Output is correct
6 Correct 253 ms 28168 KB Output is correct
7 Correct 226 ms 28192 KB Output is correct
8 Correct 204 ms 28264 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3404 KB Output is correct
11 Correct 51 ms 5408 KB Output is correct
12 Correct 47 ms 5324 KB Output is correct
13 Correct 38 ms 5272 KB Output is correct
14 Correct 36 ms 5344 KB Output is correct
15 Correct 37 ms 5280 KB Output is correct
16 Correct 39 ms 5312 KB Output is correct
17 Correct 39 ms 4904 KB Output is correct
18 Correct 59 ms 4932 KB Output is correct
19 Correct 269 ms 28632 KB Output is correct
20 Correct 293 ms 28504 KB Output is correct
21 Correct 278 ms 28664 KB Output is correct
22 Correct 258 ms 28540 KB Output is correct
23 Correct 283 ms 28532 KB Output is correct
24 Correct 273 ms 28564 KB Output is correct