oj.uz

Submission #98387

# Submission time Handle Problem Language Result Execution time Memory
98387 2019-02-22T19:44:03 Z Kastanda Park (BOI16_park) C++11
100 / 100
 1334 ms 32860 KB 
#include<bits/stdc++.h>
#define pb push_back
#define eps 1e-4
using namespace std;
typedef long double ld;
const int N = 2019;
int n, q, W, H, X[N], Y[N], R[N], P[N];
int 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(int &a, int 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] = (int)(d + eps);
        }
    /*
     ** n + 1 : bottom
     ** n + 2 : right
     ** n + 3 : top
     ** n + 4 : left
    */
    for (int i = 1; i <= n; i++)
    {
        D[i][n + 1] = D[n + 1][i] = (int)(max((ld)Y[i] - R[i], (ld)0.0000) / 2.0 + eps);
        D[i][n + 3] = D[n + 3][i] = (int)(max((ld)H - Y[i] - R[i], (ld)0.0000) / 2.0 + eps);
        D[i][n + 2] = D[n + 2][i] = (int)(max((ld)W - X[i] - R[i], (ld)0.0000) / 2.0 + eps);
        D[i][n + 4] = D[n + 4][i] = (int)(max((ld)X[i] - R[i], (ld)0.0000) / 2.0 + eps);
    }
    D[n + 1][n + 3] = D[n + 3][n + 1] = (int)(H / 2.0 + eps);
    D[n + 2][n + 4] = D[n + 4][n + 2] = (int)(W / 2.0 + eps);
    for (int i = 0; i <= 4; i++)
        for (int j = 0; j <= 4; j++)
            F[i][j] = 1e9 + 1031232;
    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;
        int 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

park.cpp: In function 'int main()':
park.cpp:23: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:25: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:97: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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 32736 KB Output is correct
2 Correct 1164 ms 32732 KB Output is correct
3 Correct 1160 ms 32604 KB Output is correct
4 Correct 1207 ms 32732 KB Output is correct
5 Correct 1271 ms 32856 KB Output is correct
6 Correct 1296 ms 32860 KB Output is correct
7 Correct 692 ms 32732 KB Output is correct
8 Correct 652 ms 32728 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 1952 KB Output is correct
2 Correct 54 ms 1964 KB Output is correct
3 Correct 85 ms 1908 KB Output is correct
4 Correct 92 ms 1884 KB Output is correct
5 Correct 53 ms 1908 KB Output is correct
6 Correct 60 ms 2036 KB Output is correct
7 Correct 47 ms 632 KB Output is correct
8 Correct 49 ms 632 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 32736 KB Output is correct
2 Correct 1164 ms 32732 KB Output is correct
3 Correct 1160 ms 32604 KB Output is correct
4 Correct 1207 ms 32732 KB Output is correct
5 Correct 1271 ms 32856 KB Output is correct
6 Correct 1296 ms 32860 KB Output is correct
7 Correct 692 ms 32732 KB Output is correct
8 Correct 652 ms 32728 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 80 ms 1952 KB Output is correct
12 Correct 54 ms 1964 KB Output is correct
13 Correct 85 ms 1908 KB Output is correct
14 Correct 92 ms 1884 KB Output is correct
15 Correct 53 ms 1908 KB Output is correct
16 Correct 60 ms 2036 KB Output is correct
17 Correct 47 ms 632 KB Output is correct
18 Correct 49 ms 632 KB Output is correct
19 Correct 1285 ms 32732 KB Output is correct
20 Correct 1264 ms 32728 KB Output is correct
21 Correct 1184 ms 32732 KB Output is correct
22 Correct 1266 ms 32732 KB Output is correct
23 Correct 1334 ms 32728 KB Output is correct
24 Correct 771 ms 32732 KB Output is correct