제출 #497834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
497834		tubesolt	Park (BOI16_park)	C++14	0 / 100	307 ms	32884 KiB

park

#include <bits/stdc++.h>
#include <math.h>
using namespace std;

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

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

struct Arista {
    int nodo, lenght;
};

Tree trees[2002];
vector <Arista> grafo[2008];
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(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
    {
        int x = queue_points.front(); // saco el proximo de la cola
        queue_points.pop();
        for (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 (int i = 1; i <= n; i++)
    {
        for (int j = i+1; j <= n; j++)
        {
            a.nodo = i;
            a.lenght = sqrt( pow(trees[i].x-trees[j].x,2.0) + pow(trees[i].y-trees[j].y,2.0) ); // - 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 (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 (int i = 1; i <= n; i++)
        cin >> trees[i].x >> trees[i].y >> trees[i].r;

    create_graph();

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


    for (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 (int i = 1; i <= m; i++)
        cout << output[i] << "\n";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'void findpaths(int, long long int)':
park.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Arista>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int i = 0; i<grafo[x].size(); i++)
      |                         ~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42