oj.uz

답안 #1095864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1095864 2024-10-03T10:45:32 Z multifanblinks Park (BOI16_park) C++17
100 / 100
 284 ms 36040 KB 
#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 = 2e3 + 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

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
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 35000 KB Output is correct
2 Correct 227 ms 35016 KB Output is correct
3 Correct 230 ms 35016 KB Output is correct
4 Correct 229 ms 35016 KB Output is correct
5 Correct 228 ms 35012 KB Output is correct
6 Correct 228 ms 35016 KB Output is correct
7 Correct 213 ms 35000 KB Output is correct
8 Correct 210 ms 35088 KB Output is correct
9 Correct 2 ms 1884 KB Output is correct
10 Correct 1 ms 2072 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 3292 KB Output is correct
2 Correct 33 ms 3036 KB Output is correct
3 Correct 32 ms 3216 KB Output is correct
4 Correct 32 ms 3184 KB Output is correct
5 Correct 32 ms 3180 KB Output is correct
6 Correct 33 ms 3288 KB Output is correct
7 Correct 28 ms 2644 KB Output is correct
8 Correct 27 ms 2652 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 35000 KB Output is correct
2 Correct 227 ms 35016 KB Output is correct
3 Correct 230 ms 35016 KB Output is correct
4 Correct 229 ms 35016 KB Output is correct
5 Correct 228 ms 35012 KB Output is correct
6 Correct 228 ms 35016 KB Output is correct
7 Correct 213 ms 35000 KB Output is correct
8 Correct 210 ms 35088 KB Output is correct
9 Correct 2 ms 1884 KB Output is correct
10 Correct 1 ms 2072 KB Output is correct
11 Correct 33 ms 3292 KB Output is correct
12 Correct 33 ms 3036 KB Output is correct
13 Correct 32 ms 3216 KB Output is correct
14 Correct 32 ms 3184 KB Output is correct
15 Correct 32 ms 3180 KB Output is correct
16 Correct 33 ms 3288 KB Output is correct
17 Correct 28 ms 2644 KB Output is correct
18 Correct 27 ms 2652 KB Output is correct
19 Correct 276 ms 35924 KB Output is correct
20 Correct 268 ms 36040 KB Output is correct
21 Correct 275 ms 36028 KB Output is correct
22 Correct 282 ms 36040 KB Output is correct
23 Correct 284 ms 36040 KB Output is correct
24 Correct 245 ms 36032 KB Output is correct