Submission #1122559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122559		AnhPham	Park (BOI16_park)	C++20	0 / 100	424 ms	102116 KiB

park

#include <bits/stdc++.h>

using namespace std;

#define int     long long
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()

const   int     MOD = (int)1e9 + 7;
const   int     INF = (int)4e18 + 18;

void solve();

int32_t main() {
#define CODE ""
    if (fopen(CODE".inp", "r"))
        freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);

    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(0);
    int testcases = 1;

#define multitest 0
    if (multitest) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/** [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] **/
/**                            The Last Dance                            **/

const int mxN = 2e3 + 3, mxM = 1e5 + 5;

int N, M, W, H;
int x[mxN], y[mxN], r[mxN];
int R[mxM], e[mxM];
int par[mxN], sz[mxN];
string ans[mxM];

struct event {
    long double dist;
    int t, x, y;
};

int root(int x) {
    if (x == par[x])
        return x;

    return par[x] = (root(par[x]));
}

void unite(int x, int y) {
    if ((x = root(x)) != (y = root(y))) {
        if (sz[x] < sz[y])
            swap(x, y);

        sz[x] += sz[y];
        par[y] = x;
    }
}

bool is_connect(int x, int y) {
    return (root(x) == root(y));
}

void solve() {
    cin >> N >> M >> W >> H; swap(W, H);

    for(int i = 1; i <= N; ++i) {
        cin >> x[i] >> y[i] >> r[i];

        swap(x[i], y[i]);
    }

    for (int i = 1; i <= M; ++i)
        cin >> R[i] >> e[i];

    for(int i = 1; i <= N; ++i)
        par[i] = i, sz[i] = 1;

    vector <event> events;
    for (int i = 1; i <= N; ++i) {
        events.push_back({ x[i] - r[i], 1, i, N + 1 });
        events.push_back({ (H - y[i]) - r[i], 1, i, N + 2 });
        events.push_back({ (W - x[i]) - r[i], 1, i, N + 3 });
        events.push_back({ y[i] - r[i], 1, i, N + 4 });
    }

    for(int i = 1; i <= M; ++i)
        events.push_back({ 2 * R[i], 0, i, 0 });

    for (int i = 1; i <= N; ++i)
        for (int j = i + 1; j <= N; ++j) {
            long double dx = x[i] - x[j];
            long double dy = y[i] - y[j];
            events.push_back({ sqrt(dx * dx + dy * dy) - r[i] - r[j], 1, i, j });
        }

    sort(all(events), [](event x, event y) {
        return x.dist < y.dist || (x.dist == y.dist && x.t < y.t);
    });

    for (auto item : events) {
        if (item.t == 1)
            unite(item.x, item.y);
        else {
            bool go1 = 1;
            bool go2 = 1;
            bool go3 = 1;
            bool go4 = 1;

            if (e[item.x] == 1) {
                if (is_connect(N + 1, N + 3))
                    go2 = go3 = 0;

                if (is_connect(N + 2, N + 4))
                    go4 = go3 = 0;

                if (is_connect(N + 1, N + 2))
                    go2 = 0;

                if (is_connect(N + 2, N + 3))
                    go3 = 0;

                if (is_connect(N + 3, N + 4))
                    go4 = 0;
            } else if (e[item.x] == 2) {
                if (is_connect(N + 1, N + 3))
                    go1 = go4 = 0;

                if (is_connect(N + 2, N + 4))
                    go4 = go3 = 0;

                if (is_connect(N + 1, N + 4))
                    go1 = 0;

                if (is_connect(N + 2, N + 3))
                    go3 = 0;

                if (is_connect(N + 3, N + 4))
                    go4 = 0;
            } else if (e[item.x] == 3) {
                if (is_connect(N + 1, N + 3))
                    go1 = go4 = 0;

                if (is_connect(N + 2, N + 4))
                    go1 = go2 = 0;

                if (is_connect(N + 1, N + 4))
                    go1 = 0;

                if (is_connect(N + 1, N + 2))
                    go2 = 0;

                if (is_connect(N + 3, N + 4))
                    go4 = 0;
            } else {
                if (is_connect(N + 1, N + 3))
                    go1 = go4 = 0;

                if (is_connect(N + 2, N + 4))
                    go1 = go2 = 0;

                if (is_connect(N + 1, N + 4))
                    go1 = 0;

                if (is_connect(N + 1, N + 2))
                    go2 = 0;

                if (is_connect(N + 2, N + 3))
                    go3 = 0;
            }

            string ret = "";
            if (go1)
                ret += '1';

            if (go2)
                ret += '2';

            if (go3)
                ret += '3';

            if (go4)
                ret += '4';

            ans[item.x] = ret;
        }
    }

    for (int i = 1; i <= M; ++i)
        cout << ans[i] << "\n";
}

Compilation message (stderr)

park.cpp: In function 'void solve()':
park.cpp:80:33: warning: narrowing conversion of '(x[i] - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   80 |         events.push_back({ x[i] - r[i], 1, i, N + 1 });
      |                            ~~~~~^~~~~~
park.cpp:81:39: warning: narrowing conversion of '((H - y[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   81 |         events.push_back({ (H - y[i]) - r[i], 1, i, N + 2 });
      |                            ~~~~~~~~~~~^~~~~~
park.cpp:82:39: warning: narrowing conversion of '((W - x[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   82 |         events.push_back({ (W - x[i]) - r[i], 1, i, N + 3 });
      |                            ~~~~~~~~~~~^~~~~~
park.cpp:83:33: warning: narrowing conversion of '(y[i] - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   83 |         events.push_back({ y[i] - r[i], 1, i, N + 4 });
      |                            ~~~~~^~~~~~
park.cpp:87:30: warning: narrowing conversion of '(2 * R[i])' from 'long long int' to 'long double' [-Wnarrowing]
   87 |         events.push_back({ 2 * R[i], 0, i, 0 });
      |                            ~~^~~~~~
park.cpp: In function 'int32_t main()':
park.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:17:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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