Submission #741954

#	Time	Username	Problem	Language	Result	Execution time	Memory
741954		MilosMilutinovic	Park (BOI16_park)	C++14	100 / 100	490 ms	68752 KiB

park

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, w, h, x[N], y[N], r[N], R[N], e[N];
int ans[N], ord[N];
struct DSU {
    int par[N], sz[N];
    void init() {
        for (int i = 1; i < N; i++) par[i] = i, sz[i] = 1;
    }
    int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        par[y] = x;
    }
    bool same(int x, int y) {  return root(x) == root(y); }
} D;
bool cmp(int i, int j) { return R[i] < R[j]; }
void rem(int& x, int y) { if (x >> y & 1) x ^= (1 << y); }
int main() {
    scanf("%d%d", &n, &m);
    scanf("%d%d", &w, &h);
    for (int i = 1; i <= n; i++) scanf("%d%d%d", &x[i], &y[i], &r[i]);
    for (int i = 1; i <= m; i++) scanf("%d%d", &R[i], &e[i]);
    D.init();
    vector<tuple<long double, int, int>> edg;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            long double dx = (x[i] - x[j]) * 1LL * (x[i] - x[j]);
            long double dy = (y[i] - y[j]) * 1LL * (y[i] - y[j]);
            long double d = sqrt(dx + dy) - r[i] - r[j];
            edg.emplace_back(d / 2, i, j);
        }
        edg.emplace_back((y[i] - r[i]) / 2, i, n + 1);
        edg.emplace_back((w - x[i] - r[i]) / 2, i, n + 2);
        edg.emplace_back((h - y[i] - r[i]) / 2, i, n + 3);
        edg.emplace_back((x[i] - r[i]) / 2, i, n + 4);
    }
    sort(edg.begin(), edg.end());
    for (int i = 1; i <= m; i++) ord[i] = i;
    sort(ord + 1, ord + m + 1, cmp);
    int ptr = 0;
    for (int _i = 1; _i <= m; _i++) {
        int i = ord[_i];
        while (ptr < edg.size() && get<0>(edg[ptr]) < R[i] * 1.0) {
            D.unite(get<1>(edg[ptr]), get<2>(edg[ptr]));
            ptr++;
        }
        if (e[i] == 1) {
            ans[i] = (1 << 4) - 1;
            if (D.same(n + 1, n + 2)) rem(ans[i], 1);
            if (D.same(n + 1, n + 3)) rem(ans[i], 1), rem(ans[i], 2);
            if (D.same(n + 2, n + 3)) rem(ans[i], 2);
            if (D.same(n + 2, n + 4)) rem(ans[i], 2), rem(ans[i], 3);
            if (D.same(n + 3, n + 4)) rem(ans[i], 3);
            if (D.same(n + 1, n + 4)) rem(ans[i], 1), rem(ans[i], 2), rem(ans[i], 3);
        }
        if (e[i] == 2) {
            ans[i] = (1 << 4) - 1;
            if (D.same(n + 1, n + 2)) rem(ans[i], 0), rem(ans[i], 2), rem(ans[i], 3);
            if (D.same(n + 1, n + 3)) rem(ans[i], 0), rem(ans[i], 3);
            if (D.same(n + 2, n + 3)) rem(ans[i], 2);
            if (D.same(n + 2, n + 4)) rem(ans[i], 2), rem(ans[i], 3);
            if (D.same(n + 3, n + 4)) rem(ans[i], 3);
            if (D.same(n + 1, n + 4)) rem(ans[i], 0);
        }
        if (e[i] == 3) {
            ans[i] = (1 << 4) - 1;
            if (D.same(n + 1, n + 2)) rem(ans[i], 1);
            if (D.same(n + 1, n + 3)) rem(ans[i], 0), rem(ans[i], 3);
            if (D.same(n + 2, n + 3)) rem(ans[i], 0), rem(ans[i], 1), rem(ans[i], 3);
            if (D.same(n + 2, n + 4)) rem(ans[i], 0), rem(ans[i], 1);
            if (D.same(n + 3, n + 4)) rem(ans[i], 3);
            if (D.same(n + 1, n + 4)) rem(ans[i], 0);
        }
        if (e[i] == 4) {
            ans[i] = (1 << 4) - 1;
            if (D.same(n + 1, n + 2)) rem(ans[i], 1);
            if (D.same(n + 1, n + 3)) rem(ans[i], 1), rem(ans[i], 2);
            if (D.same(n + 2, n + 3)) rem(ans[i], 2);
            if (D.same(n + 2, n + 4)) rem(ans[i], 0), rem(ans[i], 1);
            if (D.same(n + 3, n + 4)) rem(ans[i], 0), rem(ans[i], 1), rem(ans[i], 2);
            if (D.same(n + 1, n + 4)) rem(ans[i], 0);
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < 4; j++) {
            if (ans[i] >> j & 1) cout << j + 1;
        }
        cout << '\n';
    }
    return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long double, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while (ptr < edg.size() && get<0>(edg[ptr]) < R[i] * 1.0) {
      |                ~~~~^~~~~~~~~~~~
park.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
park.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d%d", &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~
park.cpp:27:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     for (int i = 1; i <= n; i++) scanf("%d%d%d", &x[i], &y[i], &r[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:28:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     for (int i = 1; i <= m; i++) scanf("%d%d", &R[i], &e[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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