Submission #446803

#	Time	Username	Problem	Language	Result	Execution time	Memory
446803		prvocislo	Park (BOI16_park)	C++17	100 / 100	419 ms	25440 KiB

park

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 2005, inf = 1e9 + 5;
int p[maxn], maxi[4][4], ans[4][4];
int root(int x) { return x == p[x] ? x : p[x] = root(p[x]); }
bool merge(int x, int y)
{
    x = root(x), y = root(y);
    if (x ^ y) return p[x] = y, true;
    return false;
}
struct circle { int x, y, r; } s[maxn];
ld dist(const circle &c1, const circle &c2) 
{ 
    ld x1 = c1.x, y1 = c1.y, x2 = c2.x, y2 = c2.y;
    if (c1.x == -1) x1 = x2;
    if (c1.y == -1) y1 = y2;
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)); 
}
struct edge { int u, v, d; };
bool cmp(const edge &a, const edge &b) { return a.d < b.d; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) if (i^j) maxi[i][j] = inf;
    int n, q, w, h;
    cin >> n >> q >> w >> h;
    s[0].x = -1, s[0].y =  0, s[0].r = 0;
    s[1].x =  w, s[1].y = -1, s[1].r = 0;
    s[2].x = -1, s[2].y =  h, s[2].r = 0;
    s[3].x =  0, s[3].y = -1, s[3].r = 0;
    vector<edge> e;
    for (int i = 4; i < n + 4; i++)
    {
        cin >> s[i].x >> s[i].y >> s[i].r;
        for (int j = 0; j < i; j++)
        {
            ld d = dist(s[j], s[i]) - (ld)s[i].r - (ld)s[j].r;
            e.push_back({j, i, (int)(d/2.)});
        }
    }
    for (int i = 0; i < n + 4; i++) p[i] = i;
    sort(e.begin(), e.end(), cmp);
    /*cout << endl;
    for (int i = 0; i < e.size(); i++) cout << e[i].u << " " << e[i].v << " " << e[i].d << endl;
    cout << endl;*/
    for (int i = 0; i < e.size(); i++) if (merge(e[i].u, e[i].v))
    {
        for (int e1 = 0; e1 < 4; e1++) for (int e2 = 0; e2 < e1; e2++) if (root(e1) == root(e2))
            maxi[e1][e2] = min(maxi[e1][e2], e[i].d);
    }
    /*for (int e1 = 0; e1 < 4; e1++) for (int e2 = 0; e2 < 4; e2++)
    {
        cout << maxi[e1][e2] << " ";
        if (e2 == 3) cout << endl;
    }*/
    for (int e1 = 0; e1 < 4; e1++) for (int e2 = e1+1; e2 < 4; e2++) maxi[e1][e2] = maxi[e2][e1];
    ans[0][1] = ans[1][0] = min({maxi[0][2], maxi[0][3], maxi[0][1]});
    ans[1][2] = ans[2][1] = min({maxi[1][3], maxi[0][1], maxi[1][2]});
    ans[2][3] = ans[3][2] = min({maxi[0][2], maxi[2][3], maxi[2][1]});
    ans[3][0] = ans[0][3] = min({maxi[1][3], maxi[3][2], maxi[3][0]});
    ans[0][2] = ans[2][0] = min({maxi[0][2], maxi[3][1], maxi[0][3], maxi[1][2]});
    ans[3][1] = ans[1][3] = min({maxi[0][2], maxi[3][1], maxi[0][1], maxi[2][3]});
    /*for (int e1 = 0; e1 < 4; e1++) for (int e2 = 0; e2 < 4; e2++)
    {
        cout << ans[e1][e2] << " ";
        if (e2 == 3) cout << endl;
    }*/
    for (int i = 0; i < 4; i++) ans[i][i] = inf;
    while (q--)
    {
        int r, c;
        cin >> r >> c;
        c--;
        for (int i = 0; i < 4; i++) if (ans[c][i] >= r)
            cout << i+1;
        cout << "\n";
    }
    return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i < e.size(); i++) if (merge(e[i].u, e[i].v))
      |                     ~~^~~~~~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42