Submission #1122640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122640		AnhPham	Park (BOI16_park)	C++20	58 / 100	2598 ms	68508 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(false);
    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 = 2002, mxM = 1e5 + 5;

struct POT {
    int x, y, r;
};

struct EDGE {
    int v, c;
};

int N, M, W, H;
POT pots[mxN];
vector <EDGE> adj[mxN + 4];
string ans[mxM];
int vst[mxN + 4];

void bfs(int st, int maxsize) {
    memset(vst, 0, sizeof vst); vst[st] = 1;
    queue <int> qu; qu.push(st);
    while (!qu.empty()) {
        int u = qu.front(); qu.pop();
        for (int i = 0; i < sz(adj[u]); i++)
            if (vst[adj[u][i].v] == 0) {
                if (adj[u][i].c < maxsize) {
                    vst[adj[u][i].v] = 1;
                    qu.push(adj[u][i].v);
                } else
                    break;
            }
    }
}


int sqr(int x) {
    return x * x;
}

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

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

    for (int i = 1; i <= N; ++i) {
        EDGE e;
        for (int j = i + 1; j <= N; ++j) {
            e.c = sqrt((long double)(sqr(pots[i].x - pots[j].x) + sqr(pots[i].y - pots[j].y))) - pots[i].r - pots[j].r;
            e.v = i;
            adj[j].push_back(e);
            e.v = j;
            adj[i].push_back(e);
        }
        e.c = H - pots[i].y - pots[i].r;
        e.v = i;
        adj[N + 1].push_back(e);
        e.v = N + 1;
        adj[i].push_back(e);

        e.c = W - pots[i].x - pots[i].r;
        e.v = i;
        adj[N + 2].push_back(e);
        e.v = N + 2;
        adj[i].push_back(e);

        e.c = pots[i].y - pots[i].r;
        e.v = i;
        adj[N + 3].push_back(e);
        e.v = N + 3;
        adj[i].push_back(e);

        e.c = pots[i].x - pots[i].r;
        e.v = i;
        adj[N + 4].push_back(e);
        e.v = N + 4;
        adj[i].push_back(e);
    }

    for (int i = 1; i <= N + 4; ++i)
        sort(all(adj[i]), [&](const EDGE &lhs, const EDGE &rhs) -> bool {
            return lhs.c < rhs.c;
        });

    for (int r, e, i = 1; i <= M; ++i) {
        cin >> r >> e;

        r = r * 2;
        int go1 = 1;
        int go2 = 1;
        int go3 = 1;
        int go4 = 1;

        bfs(N + 1, r);
        if (e == 1) {
            if (vst[N + 3]) go3 = go2 = 0;
            if (vst[N + 2]) go3 = 0;
            if (vst[N + 4]) go4 = 0;
        } else if (e == 2) {
            if (vst[N + 3]) go4 = go1 = 0;
            if (vst[N + 2]) go3 = 0;
            if (vst[N + 4]) go4 = 0;
        } else if (e == 3) {
            if (vst[N + 3]) go4 = go1 = 0;
            if (vst[N + 2]) go1 = go2 = go4 = 0;
            if (vst[N + 4]) go4 = 0;
        } else if (e == 4) {
            if (vst[N + 3]) go2 = go3 = 0;
            if (vst[N + 2]) go3 = 0;
            if (vst[N + 4]) go1 = go2 = go3 = 0;
        }

        if (go1 + go2 + go3 + go4 > 1) {
            bfs(N + 2, r);
            if (e == 1) {
                if (vst[N + 3]) go2 = 0;
                if (vst[N + 4]) go3 = go4 = 0;
            } else if (e == 2) {
                if (vst[N + 3]) go1 = go3 = go4 = 0;
                if (vst[N + 4]) go3 = go4 = 0;
            } else if (e == 3) {
                if (vst[N + 3]) go2 = 0;
                if (vst[N + 4]) go1 = go2 = 0;
            } else if (e == 4) {
                if (vst[N + 3]) go2 = 0;
                if (vst[N + 4]) go1 = go2 = 0;
            }
        }

        if (go1 + go2 + go3 + go4 > 1) {
           bfs(N + 3, r);
           if (e == 1) {
               if (vst[N + 4]) go2 = go3 = go4 = 0;
           } else if (e == 2) {
               if (vst[N + 4]) go1 = 0;
           } else if (e == 3) {
               if (vst[N + 4]) go1 = 0;
           } else if (e == 4) {
               if (vst[N + 4]) go1 = 0;
           }
        }

        string ret = "";
        if (go1) ret += "1";
        if (go2) ret += "2";
        if (go3) ret += "3";
        if (go4) ret += "4";

        ans[i] = ret;
    }

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

Compilation message (stderr)

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: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 0 / 42