Submission #1095861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095861		multifanblinks	Park (BOI16_park)	C++17	31 / 100	279 ms	67704 KiB

park

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ep emplace
#define mp make_pair
#define rg(v) (v).begin(), (v).end()
#define rgb(v) (v).begin(), (v).end(), (v).begin()
#define mset(a, s) memset(a, s, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#ifndef __cpp_lib_ssize
#define ssize(v) static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype((v).size())>>>((v).size())
#endif
#ifndef __cpp_lib_gcd_lcm
#define gcd __gcd
#define lcm __lcm
#endif

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const unsigned N = 1e3 + 10, M = 1e5 + 10;

int n, m, dsu[N], result[M];
vector<pii> b[3] = {
    {{0, 1}, {0, 2}, {0, 3}},
    {{0, 2}, {0, 3}, {1, 2}, {1, 3}},
    {{0, 3}, {1, 3}, {2, 3}}};
ll w, h;
struct circle
{
    ll x, y, r;
    circle(ll x = 0, ll y = 0, ll r = 0) : x(x), y(y), r(r) {}
} c[N];
struct query
{
    ll r;
    int c, i;
    query(int r = 0, int c = 0, int i = 0) : r(r), c(c), i(i) {}
    friend bool operator<(const query &lhs, const query &rhs)
    {
        return lhs.r < rhs.r;
    }
} a[M];
struct node
{
    int u, v;
    db d;
    node(int u = 0, int v = 0, db d = 0.0) : u(u), v(v), d(d) {}
    friend bool operator<(const node &lhs, const node &rhs)
    {
        return lhs.d < rhs.d;
    }
};
vector<node> q;

db dist(const circle &lhs, const circle &rhs)
{
    return sqrt((rhs.x - lhs.x) * (rhs.x - lhs.x) + (rhs.y - lhs.y) * (rhs.y - lhs.y)) - lhs.r - rhs.r;
}

int par(int u)
{
    return dsu[u] < 0 ? u : dsu[u] = par(dsu[u]);
}

bool uni(int u, int v)
{
    u = par(u);
    v = par(v);
    if (u == v)
        return false;
    if (dsu[u] > dsu[v])
        swap(u, v);
    dsu[u] += dsu[v];
    dsu[v] = u;
    return true;
}

bool is_uni(int u, int v)
{
    return par(u) == par(v);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> w >> h;
    for (int i = 1; i <= n; ++i)
        cin >> c[i].x >> c[i].y >> c[i].r;

    for (int i = 1; i <= m; ++i)
    {
        cin >> a[i].r >> a[i].c;
        a[i].i = i;
    }

    for (int i = 1; i <= n; ++i)
    {
        q.eb(i, n + 1, dist(c[i], circle(c[i].x, 0, 0)));
        q.eb(i, n + 2, dist(c[i], circle(w, c[i].y, 0)));
        q.eb(i, n + 3, dist(c[i], circle(c[i].x, h, 0)));
        q.eb(i, n + 4, dist(c[i], circle(0, c[i].y, 0)));
        for (int j = i + 1; j <= n; ++j)
            q.eb(i, j, dist(c[i], c[j]));
    }

    mset(dsu, -1);
    sort(rg(q));
    sort(a + 1, a + m + 1);
    fill_n(result + 1, m, 0b11110);

    // for (auto &&i : q)
    //     cerr << i.u << ' ' << i.v << ' ' << i.d << '\n';
    // cerr << '\n';
    int t = 0;
    for (int i = 1; i <= m; ++i)
    {
        while (t < q.size() && q[t].d < 2 * a[i].r)
        {
            uni(q[t].u, q[t].v);
            ++t;
        }
        // cerr << a[i].r << ' ' << a[i].c << ' ' << t << '\n';

        auto &res = result[a[i].i];

        for (int j = 0, en = a[i].c; j < 3; ++j)
        {
            if (++en > 4)
                en -= 4;
            for (auto [l, r] : b[j])
            {
                l += a[i].c;
                if (l > 4)
                    l -= 4;
                r += a[i].c;
                if (r > 4)
                    r -= 4;
                l += n;
                r += n;
                // cerr << "check " << a[i].c << " to " << en << " with " << l << ' ' << r << " is " << is_uni(l, r) << '\n';
                if (is_uni(l, r))
                    res &= ~(1 << en);
            }
        }
    }

    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= 4; ++j)
            if (result[i] & (1 << j))
                cout << j;
        cout << '\n';
    }

    return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         while (t < q.size() && q[t].d < 2 * a[i].r)
      |                ~~^~~~~~~~~~

• Subtask 1: 0 / 27
• Subtask 2: 31 / 31
• Subtask 3: 0 / 42