oj.uz

Submission #1096436

# Submission time Handle Problem Language Result Execution time Memory
1096436 2024-10-04T12:42:56 Z anhthi Park (BOI16_park) C++14
100 / 100
 327 ms 52008 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)

template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }

template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }

template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }

int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}

const ll oo = (ll) 1e17;
const int inf = (ll) 2e9 + 7, mod = (ll) 123456789;

const int N = 1e5 + 15, BASE = 307;

void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }

ll n, q, w, h;
ll x[N], y[N], r[N];

array<ll, 3> query[N];
vector<array<ll, 3>> e;

ll sqr(ll x) { return 1LL * x * x; }

ll dist(int i, int j) {
    return sqrtl(sqr(x[i] - x[j]) + sqr(y[i] - y[j])) - r[i] - r[j];
}

struct dsu {
    vector<ll> par, sz;
    dsu(ll n) {
        par.resize(n + 5);
        sz.resize(n + 5, 1);
        rep(i, n) par[i] = i;
    }
    ll root(ll u) {
        return u == par[u] ? u : par[u] = root(par[u]);
    }
    void unite(ll u, ll v) {
        u = root(u);
        v = root(v);
        if (u == v) return;
        if (sz[u] < sz[v])
            swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
        return;
    }
    bool connect(ll u, ll v) {
        return root(u) == root(v);
    }
};

bool res[N][5];
vector<pair<ll, ll>> state[5][5];

signed main(void) {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> q >> w >> h;
    forn(i, 1, n) {
        cin >> x[i] >> y[i] >> r[i];
        e.pb({x[i] - r[i], n + 1, i});
        e.pb({h - y[i] - r[i], n + 2, i});
        e.pb({w - x[i] - r[i], n + 3, i});
        e.pb({y[i] - r[i], n + 4, i});
    }
    forn(i, 1, n) forn(j, i + 1, n) e.pb({dist(i, j), i, j});

    sort(all(e));
    rep(i, q) {
        forn(j, 0, 1) {
            cin >> query[i][j];
        }
        query[i][2] = i;
        query[i][0] *= 2;
    }
    sort(query + 1, query + 1 + q);

    state[1][2] = { {n + 2, n + 4}, {n + 1, n + 4}, {n + 4, n + 3} };
    state[1][3] = { {n + 1, n + 3}, {n + 4, n + 2}, {n + 2, n + 3}, {n + 1, n + 4} };
    state[1][4] = { {n + 1, n + 3}, {n + 1, n + 4}, {n + 1, n + 2} };
    state[2][3] = { {n + 1, n + 3}, {n + 4, n + 3}, {n + 3, n + 2} };
    state[2][4] = { {n + 1, n + 3}, {n + 2, n + 4}, {n + 4, n + 3}, {n + 1, n + 2} };
    state[3][4] = { {n + 2, n + 3}, {n + 2, n + 4}, {n + 1, n + 2} };

    ll ID = 0;
    dsu d(n + 4);
    forn(i, 1, q) {
        array<ll, 3> cur = query[i];
        for (; ID < sz(e) && e[ID][0] < cur[0]; ++ID)
            d.unite(e[ID][1], e[ID][2]);
        forn(nxt, 1, 4) {
            bool ok = true;
            for (pair<ll, ll> tmp : state[min(1LL * nxt, cur[1])][max(1LL * nxt, cur[1])]) {
                if (d.connect(tmp.first, tmp.second)) {
                    ok = false; break;
                }
            }
            res[cur[2]][nxt] = ok;
        }
    }

    rep(i, q) {
        forn(nxt, 1, 4) if (res[i][nxt])
            cout << nxt;
        cout << '\n';
    }

    return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 49844 KB Output is correct
2 Correct 289 ms 49832 KB Output is correct
3 Correct 295 ms 49796 KB Output is correct
4 Correct 297 ms 49796 KB Output is correct
5 Correct 293 ms 49796 KB Output is correct
6 Correct 293 ms 49908 KB Output is correct
7 Correct 275 ms 49800 KB Output is correct
8 Correct 274 ms 49904 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5272 KB Output is correct
2 Correct 36 ms 5076 KB Output is correct
3 Correct 35 ms 5064 KB Output is correct
4 Correct 36 ms 5300 KB Output is correct
5 Correct 33 ms 5332 KB Output is correct
6 Correct 36 ms 5128 KB Output is correct
7 Correct 32 ms 4696 KB Output is correct
8 Correct 31 ms 4700 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 49844 KB Output is correct
2 Correct 289 ms 49832 KB Output is correct
3 Correct 295 ms 49796 KB Output is correct
4 Correct 297 ms 49796 KB Output is correct
5 Correct 293 ms 49796 KB Output is correct
6 Correct 293 ms 49908 KB Output is correct
7 Correct 275 ms 49800 KB Output is correct
8 Correct 274 ms 49904 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 36 ms 5272 KB Output is correct
12 Correct 36 ms 5076 KB Output is correct
13 Correct 35 ms 5064 KB Output is correct
14 Correct 36 ms 5300 KB Output is correct
15 Correct 33 ms 5332 KB Output is correct
16 Correct 36 ms 5128 KB Output is correct
17 Correct 32 ms 4696 KB Output is correct
18 Correct 31 ms 4700 KB Output is correct
19 Correct 321 ms 52008 KB Output is correct
20 Correct 312 ms 51796 KB Output is correct
21 Correct 319 ms 51888 KB Output is correct
22 Correct 324 ms 51800 KB Output is correct
23 Correct 327 ms 51792 KB Output is correct
24 Correct 296 ms 51952 KB Output is correct