oj.uz

Submission #741954

# Submission time Handle Problem Language Result Execution time Memory
741954 2023-05-15T07:56:30 Z MilosMilutinovic Park (BOI16_park) C++14
100 / 100
 490 ms 68752 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 436 ms 66860 KB Output is correct
2 Correct 408 ms 66952 KB Output is correct
3 Correct 407 ms 66896 KB Output is correct
4 Correct 428 ms 66936 KB Output is correct
5 Correct 419 ms 66900 KB Output is correct
6 Correct 413 ms 67000 KB Output is correct
7 Correct 400 ms 66912 KB Output is correct
8 Correct 398 ms 66980 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 1076 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4796 KB Output is correct
2 Correct 62 ms 4708 KB Output is correct
3 Correct 55 ms 4820 KB Output is correct
4 Correct 54 ms 4776 KB Output is correct
5 Correct 54 ms 4792 KB Output is correct
6 Correct 53 ms 4860 KB Output is correct
7 Correct 48 ms 4044 KB Output is correct
8 Correct 50 ms 4024 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 66860 KB Output is correct
2 Correct 408 ms 66952 KB Output is correct
3 Correct 407 ms 66896 KB Output is correct
4 Correct 428 ms 66936 KB Output is correct
5 Correct 419 ms 66900 KB Output is correct
6 Correct 413 ms 67000 KB Output is correct
7 Correct 400 ms 66912 KB Output is correct
8 Correct 398 ms 66980 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 1076 KB Output is correct
11 Correct 58 ms 4796 KB Output is correct
12 Correct 62 ms 4708 KB Output is correct
13 Correct 55 ms 4820 KB Output is correct
14 Correct 54 ms 4776 KB Output is correct
15 Correct 54 ms 4792 KB Output is correct
16 Correct 53 ms 4860 KB Output is correct
17 Correct 48 ms 4044 KB Output is correct
18 Correct 50 ms 4024 KB Output is correct
19 Correct 475 ms 68640 KB Output is correct
20 Correct 464 ms 68656 KB Output is correct
21 Correct 490 ms 68752 KB Output is correct
22 Correct 482 ms 68668 KB Output is correct
23 Correct 464 ms 68668 KB Output is correct
24 Correct 447 ms 68712 KB Output is correct