oj.uz

Submission #494598

# Submission time Handle Problem Language Result Execution time Memory
494598 2021-12-15T19:55:33 Z teruel Park (BOI16_park) C++17
100 / 100
 275 ms 28640 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.emplace_back(tri <ll> (H - x - r, i, n + 3));
        path.emplace_back(tri <ll> (W - y - r, i, n + 2));
        path.emplace_back(tri <ll> (x - r, i, n + 1));
        path.emplace_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.emplace_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 231 ms 28212 KB Output is correct
2 Correct 232 ms 28288 KB Output is correct
3 Correct 247 ms 28264 KB Output is correct
4 Correct 234 ms 28212 KB Output is correct
5 Correct 250 ms 28184 KB Output is correct
6 Correct 245 ms 28284 KB Output is correct
7 Correct 212 ms 28204 KB Output is correct
8 Correct 221 ms 28200 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 40 ms 5288 KB Output is correct
2 Correct 39 ms 5288 KB Output is correct
3 Correct 42 ms 5304 KB Output is correct
4 Correct 44 ms 5276 KB Output is correct
5 Correct 38 ms 5284 KB Output is correct
6 Correct 39 ms 5412 KB Output is correct
7 Correct 36 ms 4932 KB Output is correct
8 Correct 34 ms 4896 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 28212 KB Output is correct
2 Correct 232 ms 28288 KB Output is correct
3 Correct 247 ms 28264 KB Output is correct
4 Correct 234 ms 28212 KB Output is correct
5 Correct 250 ms 28184 KB Output is correct
6 Correct 245 ms 28284 KB Output is correct
7 Correct 212 ms 28204 KB Output is correct
8 Correct 221 ms 28200 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3404 KB Output is correct
11 Correct 40 ms 5288 KB Output is correct
12 Correct 39 ms 5288 KB Output is correct
13 Correct 42 ms 5304 KB Output is correct
14 Correct 44 ms 5276 KB Output is correct
15 Correct 38 ms 5284 KB Output is correct
16 Correct 39 ms 5412 KB Output is correct
17 Correct 36 ms 4932 KB Output is correct
18 Correct 34 ms 4896 KB Output is correct
19 Correct 275 ms 28640 KB Output is correct
20 Correct 272 ms 28532 KB Output is correct
21 Correct 268 ms 28632 KB Output is correct
22 Correct 274 ms 28504 KB Output is correct
23 Correct 269 ms 28504 KB Output is correct
24 Correct 263 ms 28552 KB Output is correct