Submission #1122625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122625		AnhPham	Park (BOI16_park)	C++20	0 / 100	433 ms	102144 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 + 10, 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) {
    x = root(x), y = root(y);
    if (x != y) {
        if (sz[x] < sz[y])
            swap(x, y);

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

bool bound(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 + 4; ++i)
            par[i] = i, sz[i] = 1;

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

    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 <= 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 });
        }
    }

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

    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 (bound(N + 1, N + 3)) go2 = go3 = 0;
                if (bound(N + 2, N + 4)) go4 = go3 = 0;
                if (bound(N + 1, N + 2)) go2 = 0;
                if (bound(N + 2, N + 3)) go3 = 0;
                if (bound(N + 3, N + 4)) go4 = 0;
            } else if (e[item.x] == 2) {
                if (bound(N + 1, N + 3)) go1 = go4 = 0;
                if (bound(N + 2, N + 4)) go4 = go3 = 0;
                if (bound(N + 1, N + 4)) go1 = 0;
                if (bound(N + 2, N + 3)) go3 = 0;
                if (bound(N + 3, N + 4)) go4 = 0;
            } else if (e[item.x] == 3) {
                if (bound(N + 1, N + 3)) go1 = go4 = 0;
                if (bound(N + 2, N + 4)) go1 = go2 = 0;
                if (bound(N + 1, N + 4)) go1 = 0;
                if (bound(N + 1, N + 2)) go2 = 0;
                if (bound(N + 3, N + 4)) go4 = 0;
            } else{
                if (bound(N + 1, N + 3)) go1 = go4 = 0;
                if (bound(N + 2, N + 4)) go1 = go2 = 0;
                if (bound(N + 1, N + 4)) go1 = 0;
                if (bound(N + 1, N + 2)) go2 = 0;
                if (bound(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:77:33: warning: narrowing conversion of '(x[i] - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   77 |         events.push_back({ x[i] - r[i], 1, i, N + 1 });
      |                            ~~~~~^~~~~~
park.cpp:78:39: warning: narrowing conversion of '((H - y[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   78 |         events.push_back({ (H - y[i]) - r[i], 1, i, N + 2 });
      |                            ~~~~~~~~~~~^~~~~~
park.cpp:79:39: warning: narrowing conversion of '((W - x[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   79 |         events.push_back({ (W - x[i]) - r[i], 1, i, N + 3 });
      |                            ~~~~~~~~~~~^~~~~~
park.cpp:80:33: warning: narrowing conversion of '(y[i] - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   80 |         events.push_back({ y[i] - r[i], 1, i, N + 4 });
      |                            ~~~~~^~~~~~
park.cpp:93:31: warning: narrowing conversion of 'R[i]' from 'long long int' to 'long double' [-Wnarrowing]
   93 |         events.push_back({ 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