oj.uz

Submission #986570

# Submission time Handle Problem Language Result Execution time Memory
986570 2024-05-20T19:00:45 Z andrei_iorgulescu Park (BOI16_park) C++14
100 / 100
 441 ms 50144 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e9;

struct tree
{
    int x,y,r;
};

int n,m,w,h;
tree a[2005];
int max_radius[5][5];///raza maxima pentru a putea ajunge de la intrarea i la intrarea j

struct edge
{
    int x,y,timp;
};

bool cmp(edge A,edge B)
{
    return A.timp < B.timp;
}

vector<edge> e;
int t[2005],sz[2005];

int tata(int x)
{
    while (x != t[x])
        x = t[x];
    return x;
}

void join(int x,int y)
{
    x = tata(x);
    y = tata(y);
    if (x == y)
        return;
    if (sz[x] < sz[y])
        swap(x,y);
    t[y] = x;
    sz[x] += sz[y];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> w >> h;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y >> a[i].r;
    for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++)
            max_radius[i][j] = inf;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            edge aux;
            aux.x = i;
            aux.y = j;
            ///2 * R + r1 + r2 >= sqrt((x1 - x2)^2 + (y1 - y2)^2), deci R = (dist(i,j) - r1 - r2) / 2 rounded up
            long double dst = sqrt((long double)((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y))) - a[i].r - a[j].r;
            dst /= 2.0d;
            aux.timp = (int)dst + 1;
            e.push_back(aux);
        }
    }
    ///n + 1 -> jos, n + 2 -> stanga, n + 3 -> sus, n + 4 -> dreapta
    for (int i = 1; i <= n; i++)
    {
        edge aux;
        aux.x = i;
        aux.y = n + 1;
        int dv = a[i].y - a[i].r;
        aux.timp = dv / 2 + 1;
        e.push_back(aux);
        aux.y = n + 3;
        dv = h - (a[i].y + a[i].r);
        aux.timp = dv / 2 + 1;
        e.push_back(aux);
        aux.y = n + 2;
        dv = a[i].x - a[i].r;
        aux.timp = dv / 2 + 1;
        e.push_back(aux);
        aux.y = n + 4;
        dv = w - (a[i].x + a[i].r);
        aux.timp = dv / 2 + 1;
        e.push_back(aux);
    }
    sort(e.begin(),e.end(),cmp);
    for (int i = 1; i <= n + 4; i++)
        t[i] = i,sz[i] = 1;
    for (auto it : e)
    {
        int x = it.x,y = it.y,z = it.timp;
        join(x,y);
        int t1 = tata(n + 1),t2 = tata(n + 2),t3 = tata(n + 3),t4 = tata(n + 4);
        if (t1 == t3 or t1 == t2 or t1 == t4)
            max_radius[1][2] = min(max_radius[1][2],z - 1);
        if (t2 == t4 or t2 == t1 or t2 == t3)
            max_radius[1][4] = min(max_radius[1][4],z - 1);
        if (t1 == t3 or t2 == t4 or t1 == t2 or t3 == t4)
            max_radius[1][3] = min(max_radius[1][3],z - 1);
        if (t2 == t4 or t4 == t1 or t4 == t3)
            max_radius[2][3] = min(max_radius[2][3],z - 1);
        if (t1 == t3 or t2 == t4 or t1 == t4 or t2 == t3)
            max_radius[2][4] = min(max_radius[2][4],z - 1);
        if (t1 == t3 or t2 == t3 or t3 == t4)
            max_radius[3][4] = min(max_radius[3][4],z - 1);
    }
    for (int i = 4; i >= 1; i--)
        for (int j = i - 1; j >= 1; j--)
            max_radius[i][j] = max_radius[j][i];
    for (int i = 1; i <= m; i++)
    {
        int r,c;
        cin >> r >> c;
        for (int j = 1; j <= 4; j++)
        {
            if (max_radius[c][j] >= r)
                cout << j;
        }
        cout << '\n';
    }
    return 0;
}

/**
Pentru fiecare pereche de puncte (s,f) neordonata (6 posibile), caut binar cat trebuie ca sa se poata merge intre astea doua
Acum, am ~180 query-uri in loc de M, ceea ce pare mult mai decent
Nu as putea chiar sa ma jur, dar cred ca pot considera efectiv raza fiecarui cerc marita cu R si laturile dreptunghiurilor pushate cu R
Acum, sunt doar un punct care vrea tehnic sa mearga din (0,0) in (h,w) (unde asta inseamna (R,R) in (h - R,w - R))
Pentru a nu putea sa merg, trebuie sa se creeze o "blocada"
Imi fac un graf cu nod pentru fiecare cerc si fiecare latura a dreptunghiului, si doua noduri care se intersecteaza in >= 2 puncte au muchie
Exista o blocada daca sunt in aceeasi componenta niste noduri laterale a.i imi blocheaza accesul intre s si f
Pentru a-mi face graful brain-deadly pot face un mare O(n^2) si am vreo n^2 * 6 * 30, n^2 * 180, 720 * 10^6 meh nush daca prea intra
Oricum macar merge pe toate subtaskurile in afara de full
Faza e, muchiile mele apar pentru un R >= r[muchie], deci am n^2 grafuri existente, tin gen dsu sau cv, si la fiecare graf vad ce perechi nu mai merg
Pot face de exemplu cu small to large si am n^2log + n^2 * 6 (query de componenta conexa in O(1)) si O(1) pe query, W
**/

/**
So... to sum up
Pentru fiecare pereche de cercuri si pereche (cerc, latura) tin minte R-ul la care se unesc
Pornesc cu un graf de N + 4 noduri initial fara muchii, in care adaug muchii pe masura ce cresc R-ul
Dupa ce am adaugat fiecare muchie, o sa am niste perechi de laturi unite => niste perechi de intrari care nu mai merg
Pentru fiecare pereche de intrari tin primul moment in care nu mai merg si imi retin asta, la query raspund penal O(1)
Acolo tin un dsu (hai ca incerc legit dsu ca probabil intra oricum) pentru join si query de cc
**/

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 49804 KB Output is correct
2 Correct 405 ms 49856 KB Output is correct
3 Correct 429 ms 49860 KB Output is correct
4 Correct 417 ms 49868 KB Output is correct
5 Correct 424 ms 49832 KB Output is correct
6 Correct 404 ms 49860 KB Output is correct
7 Correct 345 ms 49828 KB Output is correct
8 Correct 357 ms 49792 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2252 KB Output is correct
2 Correct 27 ms 2256 KB Output is correct
3 Correct 30 ms 2516 KB Output is correct
4 Correct 26 ms 2252 KB Output is correct
5 Correct 26 ms 2440 KB Output is correct
6 Correct 28 ms 2516 KB Output is correct
7 Correct 28 ms 1704 KB Output is correct
8 Correct 23 ms 1868 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 49804 KB Output is correct
2 Correct 405 ms 49856 KB Output is correct
3 Correct 429 ms 49860 KB Output is correct
4 Correct 417 ms 49868 KB Output is correct
5 Correct 424 ms 49832 KB Output is correct
6 Correct 404 ms 49860 KB Output is correct
7 Correct 345 ms 49828 KB Output is correct
8 Correct 357 ms 49792 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 27 ms 2252 KB Output is correct
12 Correct 27 ms 2256 KB Output is correct
13 Correct 30 ms 2516 KB Output is correct
14 Correct 26 ms 2252 KB Output is correct
15 Correct 26 ms 2440 KB Output is correct
16 Correct 28 ms 2516 KB Output is correct
17 Correct 28 ms 1704 KB Output is correct
18 Correct 23 ms 1868 KB Output is correct
19 Correct 416 ms 50104 KB Output is correct
20 Correct 417 ms 50100 KB Output is correct
21 Correct 441 ms 50144 KB Output is correct
22 Correct 427 ms 50072 KB Output is correct
23 Correct 431 ms 50084 KB Output is correct
24 Correct 371 ms 49924 KB Output is correct