#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;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |