oj.uz

Submission #86056

# Submission time Handle Problem Language Result Execution time Memory
86056 2018-11-24T10:09:29 Z Flying_dragon_02 Park (BOI16_park) C++14
100 / 100
 647 ms 81048 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 2010;

int n, m, pSet[N];

long double x[N], y[N], r[N], side[N][N], ans[N][N];

long double w, h;

vector<pair<long double, ii>> edge;

long double dist(long double a, long double b) {
    return sqrtl(a * a + b * b);
}

int findSet(int u) {
    if(u == pSet[u]) return u;
    else return pSet[u] = findSet(pSet[u]);
}

void unionSet(int u, int v, long double len) {
    //cout << u << " " << v << "\n";
    u = findSet(u); v = findSet(v);
    if(u == v) return ;
    //cout << u << " " << v << "\n";
    for(int i = n + 1; i <= n + 4; i++) {
        if(findSet(i) != u) continue ;
        for(int j = n + 1; j <= n + 4; j++) {
            if(findSet(j) != v) continue ;
            //cout << i << " " << j << "\n";
            side[i - n][j - n] = len;
            side[j - n][i - n] = len;
        }
    }
    //cout << u << " " << v << "\n";
    pSet[u] = v;
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n >> m;
    cin >> w >> h;
    for(int i = 1; i <= n; i++)
        cin >> x[i] >> y[i] >> r[i];
    for(int i = 1; i <= n + 4; i++)
        pSet[i] = i;
    for(int i = 1; i <= n; i++) {
        long double lmao;
        for(int j = i + 1; j <= n; j++) {
            lmao = dist(x[i] - x[j], y[i] - y[j]) - r[i] - r[j];
            lmao /= 2.0;
            edge.pb({lmao, {i, j}});
        }
        lmao = (x[i] - r[i]) / 2.0;
        edge.pb({lmao, {i, n + 1}});
        lmao = (y[i] - r[i]) / 2.0;
        edge.pb({lmao, {i, n + 2}});
        lmao = (w - x[i] - r[i]) / 2.0;
        edge.pb({lmao, {i, n + 3}});
        lmao = (h - y[i] - r[i]) / 2.0;
        edge.pb({lmao, {i, n + 4}});
    }
    sort(edge.begin(), edge.end());
    for(int i = 0; i < edge.size(); i++) {
        //cout << edge[i].se.fi << " " << edge[i].se.se << "\n";
        unionSet(edge[i].se.fi, edge[i].se.se, edge[i].fi);
    }
    ans[1][2] = ans[2][1] = min(side[1][2], min(side[2][3], side[2][4]));
    ans[1][4] = ans[4][1] = min(side[1][2], min(side[1][4], side[1][3]));
    ans[2][3] = ans[3][2] = min(side[3][2], min(side[3][1], side[3][4]));
    ans[3][4] = ans[4][3] = min(side[4][2], min(side[4][3], side[4][1]));
    ans[1][3] = ans[3][1] = min(min(side[1][2], side[4][3]), min(side[1][3], side[4][2]));
    ans[2][4] = ans[4][2] = min(min(side[3][2], side[4][1]), min(side[1][3], side[4][2]));
    while(m--) {
        int r, e;
        cin >> r >> e;
        for(int i = 1; i <= 4; i++) {
            if(i == e || ans[e][i] >= r)
                cout << i;
        }
        cout << "\n";
    }
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:74:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < edge.size(); i++) {
                    ~~^~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 66496 KB Output is correct
2 Correct 583 ms 66520 KB Output is correct
3 Correct 597 ms 66620 KB Output is correct
4 Correct 585 ms 66628 KB Output is correct
5 Correct 595 ms 66648 KB Output is correct
6 Correct 606 ms 66776 KB Output is correct
7 Correct 561 ms 66792 KB Output is correct
8 Correct 547 ms 66944 KB Output is correct
9 Correct 2 ms 66944 KB Output is correct
10 Correct 2 ms 66944 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 66944 KB Output is correct
2 Correct 44 ms 66944 KB Output is correct
3 Correct 44 ms 66944 KB Output is correct
4 Correct 45 ms 66944 KB Output is correct
5 Correct 46 ms 66944 KB Output is correct
6 Correct 47 ms 66944 KB Output is correct
7 Correct 41 ms 66944 KB Output is correct
8 Correct 41 ms 66944 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 66496 KB Output is correct
2 Correct 583 ms 66520 KB Output is correct
3 Correct 597 ms 66620 KB Output is correct
4 Correct 585 ms 66628 KB Output is correct
5 Correct 595 ms 66648 KB Output is correct
6 Correct 606 ms 66776 KB Output is correct
7 Correct 561 ms 66792 KB Output is correct
8 Correct 547 ms 66944 KB Output is correct
9 Correct 2 ms 66944 KB Output is correct
10 Correct 2 ms 66944 KB Output is correct
11 Correct 54 ms 66944 KB Output is correct
12 Correct 44 ms 66944 KB Output is correct
13 Correct 44 ms 66944 KB Output is correct
14 Correct 45 ms 66944 KB Output is correct
15 Correct 46 ms 66944 KB Output is correct
16 Correct 47 ms 66944 KB Output is correct
17 Correct 41 ms 66944 KB Output is correct
18 Correct 41 ms 66944 KB Output is correct
19 Correct 629 ms 76032 KB Output is correct
20 Correct 647 ms 76988 KB Output is correct
21 Correct 628 ms 78088 KB Output is correct
22 Correct 646 ms 78984 KB Output is correct
23 Correct 613 ms 80136 KB Output is correct
24 Correct 595 ms 81048 KB Output is correct