oj.uz

Submission #369377

# Submission time Handle Problem Language Result Execution time Memory
369377 2021-02-21T13:18:02 Z parsabahrami Park (BOI16_park) C++17
0 / 100
 460 ms 33380 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 = 2e3 + 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;
    scanf("%d%d%d%d", &n, &m, &w, &h);
    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];
            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;
    /*
    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:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |         scanf("%d%d%d", &x[i], &y[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:90:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |         int d, e; scanf("%d%d", &d, &e); d *= 2;
      |                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 33348 KB Output is correct
2 Correct 452 ms 33348 KB Output is correct
3 Correct 459 ms 33380 KB Output is correct
4 Correct 458 ms 33348 KB Output is correct
5 Correct 459 ms 33348 KB Output is correct
6 Correct 460 ms 33348 KB Output is correct
7 Correct 363 ms 33348 KB Output is correct
8 Incorrect 372 ms 33348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2148 KB Output is correct
2 Correct 56 ms 2148 KB Output is correct
3 Correct 55 ms 2148 KB Output is correct
4 Correct 57 ms 2148 KB Output is correct
5 Correct 75 ms 2148 KB Output is correct
6 Incorrect 60 ms 2276 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 33348 KB Output is correct
2 Correct 452 ms 33348 KB Output is correct
3 Correct 459 ms 33380 KB Output is correct
4 Correct 458 ms 33348 KB Output is correct
5 Correct 459 ms 33348 KB Output is correct
6 Correct 460 ms 33348 KB Output is correct
7 Correct 363 ms 33348 KB Output is correct
8 Incorrect 372 ms 33348 KB Output isn't correct
9 Halted 0 ms 0 KB -