Submission #369380

#	Time	Username	Problem	Language	Result	Execution time	Memory
369380		parsabahrami	Park (BOI16_park)	C++17	100 / 100	524 ms	33612 KiB

park

// 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 (stderr)

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