제출 #497842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
497842		tubesolt	Park (BOI16_park)	C++14	58 / 100	2585 ms	66172 KiB

park

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