oj.uz

Submission #497842

# Submission time Handle Problem Language Result Execution time Memory
497842 2021-12-23T23:58:56 Z tubesolt Park (BOI16_park) C++14
58 / 100
 2500 ms 66172 KB 
#include <bits/stdc++.h>
#include <math.h>
using namespace std;

long long int n, m, w, h, r, e;
long long int pared_top, pared_right, pared_bottom, pared_left;

typedef long double ld;

struct Tree {
   long long int x, y, r;
};

struct Arista {
    long long int nodo, lenght;
};

Tree trees[2002];
vector <Arista> grafo[2008];
long long int output[100002];
bool visited[2008];
/**
struct Question {
    int corner, order;
    long long int r;
};
Question questions[100002];
*/



queue<long long int> queue_points;

void findpaths(long long int start, long long int maxsize)
{

    memset(visited, 0, sizeof visited);
    queue_points.push(start);
    visited[start] = true;
    while (!queue_points.empty()) // y marco elementos hasta que la cola este vacia
    {
        long long int x = queue_points.front(); // saco el proximo de la cola
        queue_points.pop();
        for (long unsigned int i = 0; i<grafo[x].size(); i++)
            if (!visited[ grafo[x][i].nodo ])
            {
                if (grafo[x][i].lenght < maxsize)
                {
                    queue_points.push(grafo[x][i].nodo);
                    visited[grafo[x][i].nodo] = true;
                }
                else
                    break;
            }
    }
}


bool compareInterval(Arista i1, Arista i2)
{
    return (i1.lenght < i2.lenght);
}

void create_graph()
{
    Arista a;
    for (long long int i = 1; i <= n; i++)
    {
        for (long long int j = i+1; j <= n; j++)
        {
            a.nodo = i;
            a.lenght = sqrt( ld ((trees[i].x-trees[j].x)*(trees[i].x-trees[j].x) + (trees[i].y-trees[j].y)*(trees[i].y-trees[j].y)) ) - trees[i].r - trees[j].r;
            grafo[j].push_back(a);
            a.nodo = j;
            grafo[i].push_back(a);
        }

        // 0,0 es abajo-izquierda
        a.nodo = i;
        a.lenght = trees[i].y - trees[i].r;
        grafo[pared_bottom].push_back(a);
        a.nodo = pared_bottom;
        grafo[i].push_back(a);

        a.nodo = i;
        a.lenght = h - trees[i].y - trees[i].r;
        grafo[pared_top].push_back(a);
        a.nodo = pared_top;
        grafo[i].push_back(a);

        a.nodo = i;
        a.lenght = trees[i].x - trees[i].r;
        grafo[pared_left].push_back(a);
        a.nodo = pared_left;
        grafo[i].push_back(a);

        a.nodo = i;
        a.lenght = w - trees[i].x - trees[i].r;
        grafo[pared_right].push_back(a);
        a.nodo = pared_right;
        grafo[i].push_back(a);
    }

    for (long long int i = 1; i <= n+4; i++)
        sort(grafo[i].begin(),grafo[i].end(),compareInterval);

}

int main()
{
    cin >> n >> m >> w >> h;

    pared_top = n+1;
    pared_right = n+2;
    pared_bottom = n+3;
    pared_left= n+4;

    for (long long int i = 1; i <= n; i++)
        cin >> trees[i].x >> trees[i].y >> trees[i].r;

    create_graph();

/**
    for (long long int i = 1; i <= n+4; i++)
    {
        long long int kk = grafo[i].size();
        for (long long int j = 0; j < grafo[i].size(); j++)
            cout << "(" << grafo[i][j].nodo << "," << grafo[i][j].lenght << ") ";
        cout << "\n";
    }
*/


    for (long long int i = 1; i <= m; i++)
    {
       cin >> r >> e;
       r = r * 2;
       int p1 = 1;
       int p2 = 2;
       int p3 = 3;
       int p4 = 4;
       findpaths(pared_top,r);
       if (e==1)
       {
           if (visited[pared_bottom]) { p3 = 0; p2 = 0; }
           if (visited[pared_right]) p3 = 0;
           if (visited[pared_left]) p4 = 0;
       }
       else if (e==2)
       {
           if (visited[pared_bottom]) { p4 = 0; p1 = 0; }
           if (visited[pared_right]) p3 = 0;
           if (visited[pared_left]) p4 = 0;
       }
       else if (e==3)
       {
           if (visited[pared_bottom]) { p4 = 0; p1 = 0; }
           if (visited[pared_right]) { p1 = 0; p2 = 0; p4 = 0;}
           if (visited[pared_left]) p4 = 0;
       }
       else if (e==4)
       {
           if (visited[pared_bottom]) { p2 = 0; p3 = 0; }
           if (visited[pared_right]) p3 = 0;
           if (visited[pared_left]) { p1 = 0; p2 = 0; p3 = 0; }
       }
       if (p1+p2+p3+p4 > 1)
       {
           findpaths(pared_right,r);
           if (e==1)
           {
               if (visited[pared_bottom]) p2 = 0;
               if (visited[pared_left]) { p3 = 0; p4 = 0; }
           }
           else if (e==2)
           {
               if (visited[pared_bottom]) {p1 = 0; p3 = 0; p4 = 0;}
               if (visited[pared_left]) { p3 = 0; p4 = 0; }
           }
           else if (e==3)
           {
               if (visited[pared_bottom]) p2 = 0;
               if (visited[pared_left]) { p1 = 0; p2 = 0; }
           }
           else if (e==4)
           {
               if (visited[pared_bottom]) p2 = 0;
               if (visited[pared_left]) { p1 = 0; p2 = 0; }
           }
       }
       if (p1+p2+p3+p4 > 1)
       {
           findpaths(pared_bottom,r);
           if (e==1)
           {
               if (visited[pared_left]) { p2 = 0; p3 = 0; p4 = 0; }
           }
           else if (e==2)
           {
               if (visited[pared_left]) { p1 = 0; }
           }
           else if (e==3)
           {
               if (visited[pared_left]) { p1 = 0; }
           }
           else if (e==4)
           {
               if (visited[pared_left]) { p1 = 0; }
           }
       }
       if (p1 != 0) output[i] = output[i] * 10 + p1;
       if (p2 != 0) output[i] = output[i] * 10 + p2;
       if (p3 != 0) output[i] = output[i] * 10 + p3;
       if (p4 != 0) output[i] = output[i] * 10 + p4;
    }

    for (long long int i = 1; i <= m; i++)
        cout << output[i] << "\n";

    return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 65320 KB Output is correct
2 Correct 560 ms 65256 KB Output is correct
3 Correct 560 ms 65352 KB Output is correct
4 Correct 572 ms 65444 KB Output is correct
5 Correct 568 ms 65500 KB Output is correct
6 Correct 555 ms 65380 KB Output is correct
7 Correct 530 ms 65376 KB Output is correct
8 Correct 542 ms 65380 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 360 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 2268 KB Output is correct
2 Correct 632 ms 3428 KB Output is correct
3 Correct 623 ms 3284 KB Output is correct
4 Correct 592 ms 3412 KB Output is correct
5 Correct 316 ms 3364 KB Output is correct
6 Correct 1768 ms 3364 KB Output is correct
7 Correct 101 ms 2540 KB Output is correct
8 Correct 102 ms 2540 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 65320 KB Output is correct
2 Correct 560 ms 65256 KB Output is correct
3 Correct 560 ms 65352 KB Output is correct
4 Correct 572 ms 65444 KB Output is correct
5 Correct 568 ms 65500 KB Output is correct
6 Correct 555 ms 65380 KB Output is correct
7 Correct 530 ms 65376 KB Output is correct
8 Correct 542 ms 65380 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Correct 370 ms 2268 KB Output is correct
12 Correct 632 ms 3428 KB Output is correct
13 Correct 623 ms 3284 KB Output is correct
14 Correct 592 ms 3412 KB Output is correct
15 Correct 316 ms 3364 KB Output is correct
16 Correct 1768 ms 3364 KB Output is correct
17 Correct 101 ms 2540 KB Output is correct
18 Correct 102 ms 2540 KB Output is correct
19 Execution timed out 2585 ms 66172 KB Time limit exceeded
20 Halted 0 ms 0 KB -