oj.uz

Submission #369380

# Submission time Handle Problem Language Result Execution time Memory
369380 2021-02-21T13:35:56 Z parsabahrami Park (BOI16_park) C++17
100 / 100
 524 ms 33612 KB 
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 4e3 + 10;
int x[N], y[N], r[N], P[N], n, m, w, h; double ret[5][5];
vector<pair<double, pii>> vec;

inline void add_edge(double wx, int v, int u) {
    vec.push_back({wx, {u, v}});
}

int Find(int v) {
    return !P[v] ? v : P[v] = Find(P[v]);
}

void Union(int u, int v) {
    u = Find(u), v = Find(v);
    if (u == v) return;
    P[u] = v;
}

int f(int u, int v) {
    return Find(u) == Find(v);
}

int main() {
    for (int i = 0; i < 5; i++) 
        for (int j = 0; j < 5; j++) ret[i][j] = 1e9 + 10;
    scanf("%d%d%d%d", &n, &m, &w, &h);
    //add_edge(w, n + 2, n + 4);
    //add_edge(h, n + 1, n + 3);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &x[i], &y[i], &r[i]);
        add_edge(y[i] - r[i], n + 1, i);
        add_edge(h - y[i] - r[i], n + 3, i);
        add_edge(x[i] - r[i], n + 4, i);
        add_edge(w - x[i] - r[i], n + 2, i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            ll dx = 1ll * (x[i] - x[j]) * (x[i] - x[j]), dy = 1ll * (y[i] - y[j]) * (y[i] - y[j]);
            double d = sqrtl(dx + dy) - r[i] - r[j];
            assert(d >= 0.0);
            add_edge(d, i, j);
        }
    }
    sort(vec.begin(), vec.end());
    for (pair<double, pii> &o : vec) {
        int u = o.S.F, v = o.S.S; double d = o.F;
        //printf("debug %d %d\n", u, v);
        Union(u, v);
        if (f(n + 1, n + 2)) 
            for (int i = 1; i <= 4; i++) 
                ret[2][i] = min(ret[2][i], d);
        if (f(n + 1, n + 4)) 
            for (int i = 1; i <= 4; i++) 
                ret[1][i] = min(ret[1][i], d);
        if (f(n + 1, n + 3)) 
            for (int i : {1, 4}) 
                for (int j : {2, 3}) 
                    ret[i][j] = min(ret[i][j], d);
        if (f(n + 2, n + 3)) 
            for (int i = 1; i <= 4; i++) 
                ret[3][i] = min(ret[3][i], d);
        if (f(n + 2, n + 4)) 
            for (int i : {3, 4}) 
                for (int j : {1, 2}) 
                    ret[i][j] = min(ret[i][j], d);
        if (f(n + 3, n + 4)) 
            for (int i = 1; i <= 4; i++) 
                ret[4][i] = min(ret[4][i], d);
    }
    for (int i : {1, 2, 3, 4}) 
        for (int j : {1, 2, 3, 4}) 
            ret[i][j] = ret[j][i] = min(ret[i][j], ret[j][i]);
    for (int i = 1; i <= 4; i++) ret[i][i] = 1e9 + 10;
    
    /*
    for (int i = 1; i <= 4; i++) {
        for (int j = i + 1; j <= 4; j++) 
            //printf("%d %d %.5f\n", i, j, ret[i][j]);
    }
    */
    for (; m; m--) {
        int d, e; scanf("%d%d", &d, &e); d *= 2;
        for (int i = 1; i <= 4; i++) if (d <= ret[e][i]) printf("%d", i);
        printf("\n");
    }
    return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%d%d%d%d", &n, &m, &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         scanf("%d%d%d", &x[i], &y[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:94:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |         int d, e; scanf("%d%d", &d, &e); d *= 2;
      |                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 33404 KB Output is correct
2 Correct 463 ms 33332 KB Output is correct
3 Correct 474 ms 33460 KB Output is correct
4 Correct 465 ms 33348 KB Output is correct
5 Correct 458 ms 33348 KB Output is correct
6 Correct 461 ms 33356 KB Output is correct
7 Correct 376 ms 33348 KB Output is correct
8 Correct 378 ms 33356 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1124 KB Output is correct
2 Correct 61 ms 1252 KB Output is correct
3 Correct 56 ms 1124 KB Output is correct
4 Correct 56 ms 1124 KB Output is correct
5 Correct 60 ms 1144 KB Output is correct
6 Correct 60 ms 1252 KB Output is correct
7 Correct 49 ms 1900 KB Output is correct
8 Correct 50 ms 1772 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 33404 KB Output is correct
2 Correct 463 ms 33332 KB Output is correct
3 Correct 474 ms 33460 KB Output is correct
4 Correct 465 ms 33348 KB Output is correct
5 Correct 458 ms 33348 KB Output is correct
6 Correct 461 ms 33356 KB Output is correct
7 Correct 376 ms 33348 KB Output is correct
8 Correct 378 ms 33356 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 60 ms 1124 KB Output is correct
12 Correct 61 ms 1252 KB Output is correct
13 Correct 56 ms 1124 KB Output is correct
14 Correct 56 ms 1124 KB Output is correct
15 Correct 60 ms 1144 KB Output is correct
16 Correct 60 ms 1252 KB Output is correct
17 Correct 49 ms 1900 KB Output is correct
18 Correct 50 ms 1772 KB Output is correct
19 Correct 524 ms 33560 KB Output is correct
20 Correct 518 ms 33588 KB Output is correct
21 Correct 516 ms 33588 KB Output is correct
22 Correct 515 ms 33604 KB Output is correct
23 Correct 523 ms 33588 KB Output is correct
24 Correct 435 ms 33612 KB Output is correct