oj.uz

Submission #233593

# Submission time Handle Problem Language Result Execution time Memory
233593 2020-05-21T03:50:03 Z cuom1999 Park (BOI16_park) C++14
0 / 100
 346 ms 56144 KB 
#include <bits/stdc++.h>
using namespace std;

struct Circle {
    long long x, y, r;
};

double sq(double a) {
    return a * a;
}

double dist(Circle a, Circle b) {
    return sqrt(sq(a.x - b.x) + sq(a.y - b.y)) - a.r - b.r;
}

struct Edge {
    int x, y;
    double c;
    bool operator < (const Edge& e) {
        return c < e.c;
    }
};

double cost[2005][2005];
Circle circle[2005];

int lab[2005];
int getRoot(int a) {
    if (lab[a] < 0) return a;
    return lab[a] = getRoot(lab[a]);
}

void dsu(int a, int b) {
    if (lab[a] > lab[b]) swap(a, b);
    lab[a] += lab[b];
    lab[b] = a;
}

double minPath[5][5];


int main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    int n, m;
    long long w, h;

    cin >> n >> m >> w >> h;
    for (int i = 1; i <= n; i++) {
        cin >> circle[i].x >> circle[i].y >> circle[i].r;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cost[i][j] = dist(circle[i], circle[j]);
        }

        cost[i][n + 1] = circle[i].y;
        cost[i][n + 2] = w - circle[i].x;
        cost[i][n + 3] = h - circle[i].y;
        cost[i][n + 4] = circle[i].x;
    }

    vector<Edge> edges;
    for (int i = 1; i <= n + 4; i++) {
        for (int j = i + 1; j <= n + 4; j++) {
            if (i > n && j > n) cost[i][j] = 1e9;
            edges.push_back({i, j, cost[i][j]});
        }
    }

    for (int i = 1; i <= 4; i++) {
        for (int j = i + 1; j <= 4; j++) {
            minPath[i][j] = -1;
        }
    }

    memset(lab, -1, sizeof(lab));
    sort(edges.begin(), edges.end());

    for (auto &e: edges) {
        // cout << e.x << " " << e.y << " " << e.c << endl;
        int a = getRoot(e.x);
        int b = getRoot(e.y);
        if (a == b) continue;
        dsu(a, b);
        // cout << e.x << " " << e.y << " " << e.c << endl;
        for (int i = n + 1; i <= n + 4; i++) {
            for (int j = i + 1; j <= n + 4; j++) {
                if (minPath[i - n][j - n] == -1 && getRoot(i) == getRoot(j)) {
                    minPath[i - n][j - n] = minPath[j - n][i - n] = e.c;
                }
            }
        }
    }

    // for (int i = 1; i <= 4; i++) {
    //     for (int j = i + 1; j <= 4; j++) {
    //         cout << i << " " << j << " " << minPath[i][j] << endl;
    //     }
    // }

    vector<vector<double>> ans(5, vector<double>(5, 1e9));

    for (int i = 1; i <= 4; i++) {
        int j = i + 1;
        if (i == 4) j = 1;
        for (int k = 1; k <= 4; k++) {
            if (k != i) ans[i][j] = min(ans[i][j], minPath[i][k]);
        }
        ans[j][i] = ans[i][j];
    }    

    ans[1][3] = ans[3][1] = min({minPath[1][3], minPath[2][4], 
                                minPath[1][4], minPath[2][3]});

    ans[2][4] = ans[4][2] = min({minPath[1][3], minPath[2][4], 
                                minPath[1][2], minPath[3][4]});

    for (int i = 1; i <= m; i++) {
        int r, e;
        cin >> r >> e;
        for (int j = 1; j <= 4; j++) {
            if (ans[e][j] + 1e-8 >= r * 2) {
                cout << j;
            }
        }
        cout << "\n";
    }
    return 0;
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 56144 KB Output is correct
2 Incorrect 346 ms 56128 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 56144 KB Output is correct
2 Incorrect 346 ms 56128 KB Output isn't correct
3 Halted 0 ms 0 KB -