#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define repa(i, a, b) for(lli i = (a); i >= (b); --i)
#define nl "\n"
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl
#define debugarr(x, a, b) cout << #x << " = ["; rep(ii, a, b) cout << x[ii] << ", "; cout << "]" << nl
#define MAX_N 200002
int dx[4] = {0, -2, 0, 2}; // USARE COMO KAREL 0-NORTE, 1-OESTE, 2-SUR, 3-ESTE
int dy[4] = {2, 0, -2, 0};
map<pair<int, int>, int> fuentes;
vector<int> hijos[MAX_N];
int grupo[MAX_N], gfinal;
map<pair<int, int>, int> bancas;
std::vector<int> u, v, a, b;
bool imposible = false;
int comp(int a){
if (grupo[a] == a) return a;
else return grupo[a] = comp(grupo[a]);
}
bool une(int a, int b){
int ga = comp(a);
int gb = comp(b);
if (ga == gb) return false;
grupo[ga] = gb;
return true;
}
void dfs(int nodo, int padre, vector<int> &x, vector<int> &y){
rep(i, 0, 3){
if (fuentes.find({x[nodo] + dx[i], y[nodo] + dy[i]}) != fuentes.end()){ // EXISTE FUENTE EN ESA DIRECCION
int h = fuentes[{x[nodo] + dx[i], y[nodo] + dy[i]}];
if (une(nodo, h)){
// ESTOS DOS NO ESTABAN UNIDOS, ES UN NUEVO CAMINO.
u.push_back(nodo);
v.push_back(h);
int bx, by; // LAS COORDENADAS DE LA BANCA
if (x[nodo] == x[h]){ // ES UNA UNION VERTICAL
by = (y[nodo] > y[h]) ? y[h] + 1 : y[h] - 1;
bx = x[h] + 1;
if (bancas.find({bx, by}) != bancas.end()) bx = x[h] - 1; // SI ESE YA EXISTE, USA LA OTRA OPCION
}
else{ // ES UNA UNION HORIZONTAL
bx = (x[nodo] > x[h]) ? x[h] + 1 : x[h] - 1;
by = y[h] + 1;
if (bancas.find({bx, by}) != bancas.end()) by = y[h] - 1; // SI YA EXISTE, USA LA OTRA OPCION
}
a.push_back(bx);
b.push_back(by);
if (bancas.find({bx, by}) != bancas.end()){
imposible = true;
return;
}
bancas[{bx, by}] = 1;
dfs(h, nodo, x, y);
}
}
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
// AGREGA LAS FUENTES A UN MAP PARA PODER BUSCARLAS FACILMENTE
rep(i, 0, x.size() - 1) fuentes[{x[i], y[i]}] = i;
// AHORA HAZ UNA BUSQUEDA EN PROFUNDIDAD DESDE CUALQUIER FUENTE, AGREGANDO UNICAMENTE CAMINOS SI SON NECESARIOS USANDO UN UNION FIND Y ACOMODANDO LAS BANCAS DE FORMA GREEDY
rep(i, 0, x.size() - 1) grupo[i] = i; // INICIALIZA EL DSU
dfs(0, -1, x, y);
// VERIFICA SI TODOS QUEDARON UNIDOS EN EL MISMO COMPONENTE
bool ok = true;
gfinal = comp(0);
rep(i, 1, x.size() - 1) if (comp(i) != gfinal){
ok = false;
break;
}
if (!ok || imposible) return 0;
build(u, v, a, b);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
| ^
parks.cpp:86:5: note: in expansion of macro 'rep'
86 | rep(i, 0, x.size() - 1) fuentes[{x[i], y[i]}] = i;
| ^~~
parks.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
| ^
parks.cpp:89:5: note: in expansion of macro 'rep'
89 | rep(i, 0, x.size() - 1) grupo[i] = i; // INICIALIZA EL DSU
| ^~~
parks.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
| ^
parks.cpp:95:5: note: in expansion of macro 'rep'
95 | rep(i, 1, x.size() - 1) if (comp(i) != gfinal){
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
8 |
Correct |
5 ms |
4940 KB |
Output is correct |
9 |
Correct |
256 ms |
38592 KB |
Output is correct |
10 |
Correct |
21 ms |
8652 KB |
Output is correct |
11 |
Correct |
113 ms |
23688 KB |
Output is correct |
12 |
Correct |
33 ms |
10396 KB |
Output is correct |
13 |
Correct |
61 ms |
15684 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
6 ms |
5196 KB |
Output is correct |
16 |
Correct |
225 ms |
32248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
8 |
Correct |
5 ms |
4940 KB |
Output is correct |
9 |
Correct |
256 ms |
38592 KB |
Output is correct |
10 |
Correct |
21 ms |
8652 KB |
Output is correct |
11 |
Correct |
113 ms |
23688 KB |
Output is correct |
12 |
Correct |
33 ms |
10396 KB |
Output is correct |
13 |
Correct |
61 ms |
15684 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
6 ms |
5196 KB |
Output is correct |
16 |
Correct |
225 ms |
32248 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
4 ms |
4940 KB |
Output is correct |
20 |
Correct |
4 ms |
4904 KB |
Output is correct |
21 |
Correct |
4 ms |
4940 KB |
Output is correct |
22 |
Correct |
4 ms |
4940 KB |
Output is correct |
23 |
Correct |
613 ms |
77208 KB |
Output is correct |
24 |
Correct |
3 ms |
4940 KB |
Output is correct |
25 |
Correct |
5 ms |
5324 KB |
Output is correct |
26 |
Correct |
6 ms |
5616 KB |
Output is correct |
27 |
Correct |
6 ms |
5452 KB |
Output is correct |
28 |
Correct |
215 ms |
33824 KB |
Output is correct |
29 |
Incorrect |
283 ms |
40000 KB |
Solution announced impossible, but it is possible. |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
8 |
Correct |
5 ms |
4940 KB |
Output is correct |
9 |
Correct |
256 ms |
38592 KB |
Output is correct |
10 |
Correct |
21 ms |
8652 KB |
Output is correct |
11 |
Correct |
113 ms |
23688 KB |
Output is correct |
12 |
Correct |
33 ms |
10396 KB |
Output is correct |
13 |
Correct |
61 ms |
15684 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
6 ms |
5196 KB |
Output is correct |
16 |
Correct |
225 ms |
32248 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
4 ms |
4940 KB |
Output is correct |
20 |
Correct |
4 ms |
4904 KB |
Output is correct |
21 |
Correct |
4 ms |
4940 KB |
Output is correct |
22 |
Correct |
4 ms |
4940 KB |
Output is correct |
23 |
Correct |
613 ms |
77208 KB |
Output is correct |
24 |
Correct |
3 ms |
4940 KB |
Output is correct |
25 |
Correct |
5 ms |
5324 KB |
Output is correct |
26 |
Correct |
6 ms |
5616 KB |
Output is correct |
27 |
Correct |
6 ms |
5452 KB |
Output is correct |
28 |
Correct |
215 ms |
33824 KB |
Output is correct |
29 |
Incorrect |
283 ms |
40000 KB |
Solution announced impossible, but it is possible. |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
8 |
Correct |
5 ms |
4940 KB |
Output is correct |
9 |
Correct |
256 ms |
38592 KB |
Output is correct |
10 |
Correct |
21 ms |
8652 KB |
Output is correct |
11 |
Correct |
113 ms |
23688 KB |
Output is correct |
12 |
Correct |
33 ms |
10396 KB |
Output is correct |
13 |
Correct |
61 ms |
15684 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
6 ms |
5196 KB |
Output is correct |
16 |
Correct |
225 ms |
32248 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
5 ms |
4940 KB |
Output is correct |
20 |
Correct |
619 ms |
74492 KB |
Output is correct |
21 |
Correct |
657 ms |
68188 KB |
Output is correct |
22 |
Correct |
619 ms |
64696 KB |
Output is correct |
23 |
Correct |
506 ms |
54552 KB |
Output is correct |
24 |
Correct |
189 ms |
21420 KB |
Output is correct |
25 |
Correct |
193 ms |
21504 KB |
Output is correct |
26 |
Correct |
209 ms |
21512 KB |
Output is correct |
27 |
Correct |
476 ms |
43520 KB |
Output is correct |
28 |
Correct |
478 ms |
43524 KB |
Output is correct |
29 |
Incorrect |
214 ms |
21808 KB |
Solution announced impossible, but it is possible. |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
8 |
Correct |
5 ms |
4940 KB |
Output is correct |
9 |
Correct |
256 ms |
38592 KB |
Output is correct |
10 |
Correct |
21 ms |
8652 KB |
Output is correct |
11 |
Correct |
113 ms |
23688 KB |
Output is correct |
12 |
Correct |
33 ms |
10396 KB |
Output is correct |
13 |
Correct |
61 ms |
15684 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
6 ms |
5196 KB |
Output is correct |
16 |
Correct |
225 ms |
32248 KB |
Output is correct |
17 |
Correct |
574 ms |
77288 KB |
Output is correct |
18 |
Correct |
627 ms |
72948 KB |
Output is correct |
19 |
Incorrect |
577 ms |
70936 KB |
Solution announced impossible, but it is possible. |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
8 |
Correct |
5 ms |
4940 KB |
Output is correct |
9 |
Correct |
256 ms |
38592 KB |
Output is correct |
10 |
Correct |
21 ms |
8652 KB |
Output is correct |
11 |
Correct |
113 ms |
23688 KB |
Output is correct |
12 |
Correct |
33 ms |
10396 KB |
Output is correct |
13 |
Correct |
61 ms |
15684 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
6 ms |
5196 KB |
Output is correct |
16 |
Correct |
225 ms |
32248 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
4 ms |
4940 KB |
Output is correct |
20 |
Correct |
4 ms |
4904 KB |
Output is correct |
21 |
Correct |
4 ms |
4940 KB |
Output is correct |
22 |
Correct |
4 ms |
4940 KB |
Output is correct |
23 |
Correct |
613 ms |
77208 KB |
Output is correct |
24 |
Correct |
3 ms |
4940 KB |
Output is correct |
25 |
Correct |
5 ms |
5324 KB |
Output is correct |
26 |
Correct |
6 ms |
5616 KB |
Output is correct |
27 |
Correct |
6 ms |
5452 KB |
Output is correct |
28 |
Correct |
215 ms |
33824 KB |
Output is correct |
29 |
Incorrect |
283 ms |
40000 KB |
Solution announced impossible, but it is possible. |
30 |
Halted |
0 ms |
0 KB |
- |