oj.uz

답안 #98386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98386 2019-02-22T19:37:56 Z Kastanda Park (BOI16_park) C++11
0 / 100
 1453 ms 48776 KB 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef 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

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
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1265 ms 48776 KB Output is correct
2 Correct 1453 ms 48600 KB Output is correct
3 Correct 1435 ms 48576 KB Output is correct
4 Correct 1436 ms 48600 KB Output is correct
5 Correct 1395 ms 48604 KB Output is correct
6 Correct 1339 ms 48604 KB Output is correct
7 Correct 780 ms 48604 KB Output is correct
8 Correct 681 ms 48608 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Incorrect 2 ms 384 KB Output isn't correct

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 2104 KB Output is correct
2 Correct 63 ms 2072 KB Output is correct
3 Correct 54 ms 2132 KB Output is correct
4 Correct 54 ms 2164 KB Output is correct
5 Correct 58 ms 2164 KB Output is correct
6 Correct 62 ms 2164 KB Output is correct
7 Incorrect 49 ms 760 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1265 ms 48776 KB Output is correct
2 Correct 1453 ms 48600 KB Output is correct
3 Correct 1435 ms 48576 KB Output is correct
4 Correct 1436 ms 48600 KB Output is correct
5 Correct 1395 ms 48604 KB Output is correct
6 Correct 1339 ms 48604 KB Output is correct
7 Correct 780 ms 48604 KB Output is correct
8 Correct 681 ms 48608 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Incorrect 2 ms 384 KB Output isn't correct