Submission #986570

#	Time	Username	Problem	Language	Result	Execution time	Memory
986570		andrei_iorgulescu	Park (BOI16_park)	C++14	100 / 100	441 ms	50144 KiB

park

#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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42