Submission #98384

#	Time	Username	Problem	Language	Result	Execution time	Memory
98384		Kastanda	Park (BOI16_park)	C++11	100 / 100	2324 ms	81272 KiB

park

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long double ld;
const int N = 2019;
int n, q, W, H, X[N], Y[N], R[N], P[N];
ld D[N][N], F[5][5];
inline bool CMP(pair < int , int > a, pair < int , int > b)
{
    return (D[a.first][a.second] < D[b.first][b.second]);
}
int Find(int v)
{
    return (P[v] ? (P[v] = Find(P[v])) : v);
}
inline void smin(ld &a, ld b)
{
    a = min(a, b);
}
int main()
{
    scanf("%d%d%d%d", &n, &q, &W, &H);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &X[i], &Y[i], &R[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            ld d = sqrt((ld)(X[i] - X[j]) * (X[i] - X[j]) + (ld)(Y[i] - Y[j]) * (Y[i] - Y[j]));
            d = max(d - R[i] - R[j], (ld)0.000000); d /= 2.0; D[i][j] = d;
        }
    for (int i = 1; i <= n; i++)
    {
        D[i][n + 1] = D[n + 1][i] = max((ld)Y[i] - R[i], (ld)0.0000) / 2.0;
        D[i][n + 3] = D[n + 3][i] = max((ld)H - Y[i] - R[i], (ld)0.0000) / 2.0;
        D[i][n + 2] = D[n + 2][i] = max((ld)W - X[i] - R[i], (ld)0.0000) / 2.0;
        D[i][n + 4] = D[n + 4][i] = max((ld)X[i] - R[i], (ld)0.0000) / 2.0;
    }
    D[n + 1][n + 3] = D[n + 3][n + 1] = H / 2.0;
    D[n + 2][n + 4] = D[n + 4][n + 2] = W / 2.0;
    for (int i = 0; i <= 4; i++)
        for (int j = 0; j <= 4; j++)
            F[i][j] = 1e10;
    vector < pair < int , int > > E;
    for (int i = 1; i <= n + 4; i++)
        for (int j = i + 1; j <= n + 4; j++)
            if (i <= n || j <= n)
                E.pb({i, j});
    E.pb({n + 1, n + 3});
    E.pb({n + 2, n + 4});
    sort(E.begin(), E.end(), CMP);
    for (auto edge : E)
    {
        int v = edge.first, u = edge.second;
        ld d = D[v][u];
        v = Find(v);
        u = Find(u);
        if (v != u)
            P[v] = u;
        if (Find(n + 1) == Find(n + 3))
        {
            smin(F[1][2], d);
            smin(F[1][3], d);
            smin(F[2][4], d);
            smin(F[3][4], d);
        }
        if (Find(n + 2) == Find(n + 4))
        {
            smin(F[1][3], d);
            smin(F[1][4], d);
            smin(F[2][3], d);
            smin(F[2][4], d);
        }
        for (int i = 1; i <= 4; i++)
        {
            int a = n + i;
            int b = (i > 1) ? (a - 1) : (n + 4);
            if (Find(a) == Find(b))
                for (int j = 1; j <= 4; j++)
                    if (i != j)
                        smin(F[i][j], d), smin(F[j][i], d);
        }
    }
    for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++)
            smin(F[i][j], F[j][i]);
    for (; q; q --)
    {
        int r, e;
        scanf("%d%d", &r, &e);
        for (int j = 1; j <= 4; j++)
            if (r <= F[e][j])
                printf("%d", j);
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &q, &W, &H);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &X[i], &Y[i], &R[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &r, &e);
         ~~~~~^~~~~~~~~~~~~~~~

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