oj.uz

Submission #233857

# Submission time Handle Problem Language Result Execution time Memory
233857 2020-05-22T03:03:32 Z anhkha2003 Park (BOI16_park) C++14
100 / 100
 684 ms 103900 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> II;
const long double EPS = 1e-8;

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

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

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

long long h, w;
long double distEdge(Circle a, int k) {
    if (k == 4) return a.x - a.r;
    if (k == 3) return h - a.y - a.r;
    if (k == 2) return w - a.x - a.r;
    return a.y - a.r; // k == 1
}

struct Edge {
    int u, v;
    long double w;
};

bool cmp(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

int root[2005];

int findRoot(int u) {
    while (root[u] >= 0) {
        u = root[u];
    }
    return u;
}

void join(int x, int y) {
    if (root[x] > root[y]) {
        swap(x, y);
    }
    root[x] += root[y];
    root[y] = x;
}

Circle circle[2005];
long double cost[2005][2005];
long double green[5][5];
long double ans[5][5];

int main() {
    //freopen("PARK.INP", "r", stdin);
    //freopen("PARK.OUT", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m >> w >> h;

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

    vector<Edge> edges;

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cost[i][j] = distCircle(circle[i], circle[j]);
            edges.push_back({i, j, cost[i][j]});
        }

        for (int j = 1; j <= 4; j++) {
            cost[i][n + j] = distEdge(circle[i], j);
            edges.push_back({i, n + j, cost[i][n + j]});
        }
    }

    sort(edges.begin(), edges.end(), cmp);

//    for (auto &i: edges) {
//        cout << i.u << " " << i.v << " " << i.w << endl;
//    }

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

    for (auto &e: edges) {
        int x = findRoot(e.u);
        int y = findRoot(e.v);
        if (x == y) continue;

        join(x, y);

        for (int i = 1; i <= 4; i++) {
            for (int j = i + 1; j <= 4; j++) {
                if (findRoot(n + i) == findRoot(n + j) && green[i][j] == -1) {
                    green[i][j] = e.w;
                    //cout << i << " " << j << " " << green[i][j] << endl;
                }
            }
        }
    }

    // 1 -> 2: 1-2, 1-3, 1-4
    // 1 -> 3: 1-4, 1-3, 2-3, 2-4
    // 1 -> 4: 1-4, 2-4, 3-4
    // 2 -> 3: 1-2, 2-3, 2-4
    // 2 -> 4: 3-4, 1-3, 2-4, 1-2
    // 3 -> 4: 1-3, 2-3, 3-4

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

    for (int i = 1; i <= m; i++) {
        int r, e;
        cin >> r >> e;

        for (int j = 1; j <= 4; j++) {
            if (e == j) ans[e][j] = 2e9;
            if (2 * r <= ans[e][j] + EPS) {
                cout << j;
            }
        }
        cout << "\n";
    }
    return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 102360 KB Output is correct
2 Correct 637 ms 102492 KB Output is correct
3 Correct 638 ms 102360 KB Output is correct
4 Correct 647 ms 102360 KB Output is correct
5 Correct 648 ms 102360 KB Output is correct
6 Correct 641 ms 102360 KB Output is correct
7 Correct 565 ms 102440 KB Output is correct
8 Correct 555 ms 102488 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3824 KB Output is correct
2 Correct 52 ms 3696 KB Output is correct
3 Correct 49 ms 3568 KB Output is correct
4 Correct 50 ms 3716 KB Output is correct
5 Correct 51 ms 3692 KB Output is correct
6 Correct 50 ms 3824 KB Output is correct
7 Correct 44 ms 1916 KB Output is correct
8 Correct 42 ms 1912 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 102360 KB Output is correct
2 Correct 637 ms 102492 KB Output is correct
3 Correct 638 ms 102360 KB Output is correct
4 Correct 647 ms 102360 KB Output is correct
5 Correct 648 ms 102360 KB Output is correct
6 Correct 641 ms 102360 KB Output is correct
7 Correct 565 ms 102440 KB Output is correct
8 Correct 555 ms 102488 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 51 ms 3824 KB Output is correct
12 Correct 52 ms 3696 KB Output is correct
13 Correct 49 ms 3568 KB Output is correct
14 Correct 50 ms 3716 KB Output is correct
15 Correct 51 ms 3692 KB Output is correct
16 Correct 50 ms 3824 KB Output is correct
17 Correct 44 ms 1916 KB Output is correct
18 Correct 42 ms 1912 KB Output is correct
19 Correct 676 ms 103900 KB Output is correct
20 Correct 677 ms 103896 KB Output is correct
21 Correct 672 ms 103768 KB Output is correct
22 Correct 684 ms 103784 KB Output is correct
23 Correct 677 ms 103784 KB Output is correct
24 Correct 601 ms 103896 KB Output is correct