#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[6] = {0, -2, 0, 2, 2, -2}; // 0-NORTE, 1-OESTE, 2-SUR, 3-ESTE, 4-NORESTE, 5-SUROESTE
int dy[6] = {2, 0, -2, 0, 2, -2};
#define norte 0
#define oeste 1
#define sur 2
#define este 3
#define noreste 4
#define suroeste 5
map<pair<int, int>, int> fuentes;
vector<int> hijos[MAX_N];
int grupo[MAX_N], gfinal;
std::vector<int> u, v, a, b;
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){
bool hayfuente[6], diagimpar;
int fuente[6];
// VALIDA EN QUE DIRECCIONES TIENE FUENTE
rep(i, norte, suroeste) hayfuente[i] = fuentes.find({x[nodo] + dx[i], y[nodo] + dy[i]}) != fuentes.end();
// OBTEN LA FUENTE EN CADA DIRECCION
rep(i, norte, suroeste)
if (hayfuente[i]) fuente[i] = fuentes[{x[nodo] + dx[i], y[nodo] + dy[i]}];
else fuente[i] = -1;
// VALIDA EN QUE DIAGONAL ESTAS
diagimpar = (x[nodo] + y[nodo]) & 3;
// LOS CASOS QUE HAY QUE REVISAR ES CUANDO LA FUENTE QUE ESTAMOS PROCESANDO PERTENECE A UN CUADRADO DE 2x2,
// EN ESOS CASOS SE DEBE EVITAR COLOCAR LOS CAMINOS QUE COLISIONAN.
// EN PARTICULAR SE EVITARA COLOCAR LOS CAMINOS NORTE O ESTE QUE COLISIONARIAN CON UN CAMINO SUR U OESTE DE UN MISMO CUADRADO
if (hayfuente[norte] && hayfuente[este] && hayfuente[noreste]){ // EL NODO ES LA ESQUINA SUROESTE DE UN CUADRADO DE 2x2
// DEPENDIENDO DE LA DIAGONAL COLOCA UNICAMENTE EL CAMINO NORTE O EL ESTE
if (diagimpar){ // PON SOLO LAS ESTE
if (une(nodo, fuente[este])){
u.push_back(nodo);
v.push_back(fuente[este]);
a.push_back((x[nodo] + x[fuente[este]]) / 2);
b.push_back(y[nodo] + 1); // BANCA AL NORTE
}
}
else{ // PON SOLO LAS NORTE
if (une(nodo, fuente[norte])){
u.push_back(nodo);
v.push_back(fuente[norte]);
a.push_back(x[nodo] + 1); // BANCA AL ESTE
b.push_back((y[nodo] + y[fuente[norte]]) / 2);
}
}
}
else{
// SI NO ES UN CUADRO UNE LIBREMENTE AL NORTE Y AL ESTE
if (hayfuente[norte] && une(nodo, fuente[norte])){
u.push_back(nodo);
v.push_back(fuente[norte]);
b.push_back((y[nodo] + y[fuente[norte]]) / 2);
if (diagimpar) a.push_back(x[nodo] - 1);
else a.push_back(x[nodo] + 1);
}
if (hayfuente[este] && une(nodo, fuente[este])){
u.push_back(nodo);
v.push_back(fuente[este]);
a.push_back((x[nodo] + x[fuente[este]]) / 2);
if (diagimpar) b.push_back(y[nodo] + 1);
else b.push_back(y[nodo] - 1);
}
}
// AL OESTE Y AL SUR SIEMPRE PUEDES UNIR LIBREMENTE
if (hayfuente[oeste] && une(nodo, fuente[oeste])){
u.push_back(nodo);
v.push_back(fuente[oeste]);
a.push_back((x[nodo] + x[fuente[norte]]) / 2);
if (diagimpar) b.push_back(y[nodo] - 1);
else b.push_back(y[nodo] + 1);
}
if (hayfuente[sur] && une(nodo, fuente[sur])){
u.push_back(nodo);
v.push_back(fuente[sur]);
b.push_back((y[nodo] + y[fuente[sur]]) / 2);
if (diagimpar) a.push_back(x[nodo] + 1);
else a.push_back(x[nodo] - 1);
}
// DESPUES DE UNIR, CONTINUA LA DFS
rep(i, norte, este) if (hayfuente[i]) dfs(fuente[i], 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,
// SE VAN A AGREGAR CAMINOS UNICAMENTE SI SON NECESARIOS PARA QUE EL GRAFO SEA CONEXO (SE VALIDA MEDIANTE UN DSU)
// PARA ACOMODAR LAS BANCAS DE FORMA QUE NO CHOQUEN SE UTILIZAN LAS DIAGONALES, EN ESTE CASO SE USAN LAS DE TIPO (x + y),
// LA IDEA ES QUE TODOS LOS CAMINOS VERTICALES QUE QUEDEN ENTRE UN PAR DE DIAGONALES TENGAN LA BANCA DEL MISMO LADO, LO MISMO CON LOS HORIZONTALES.
// ADEMAS, LOS CAMINOS ENTRE UN PAR DE DIAGONALES Y EL PAR DE DIAGONALES INMEDIATAMENTE SIGUIENTE ALTERNAN SU LADO.
// H
// \---\---\ \ \ LAS LETRAS H CORRESPONDEN A LA BANCA DEL CAMINO HORIZONTAL
// \ |\h |\ \ \ LAS LETRAS V CORRESPONDEN A LA BANCA DEL CAMINO VERTICAL
// \V| \ |V\ \ \ LAS LETRAS h EN EL DIBUJO SON BANCAS QUE COLISIONAN
// \| h\| \ \ \
// \---\---\ \ \
// H
// LAS BANCAS ENTRE UN PAR DE DIAGONALES NUNCA VAN A COLISIONAR.
// LA UNICA FORMA DE COLISIONAR ES DOS CAMINOS HORIZONTALES O VERTICALES ENCONTRADOS EN PARES DE DIAGONALES CONSECUTIVOS.
// PARA QUE ESTO SEA POSIBLE ES FORZOSO QUE HAYA UN CUADRO DE 2x2 CON FUENTES EN LAS 4 ESQUINAS, LO CUAL NO SUCEDE EN LOS SUBTASKS 4 y 5
// POR LO QUE ESTE CODIGO RESUELVE ESOS SUBTASKS
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) return 0;
build(u, v, a, b);
return 1;
}
Compilation message
parks.cpp:141:5: warning: multi-line comment [-Wcomment]
141 | // \| h\| \ \ \
| ^
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:130:5: note: in expansion of macro 'rep'
130 | 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:149:5: note: in expansion of macro 'rep'
149 | 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:155:5: note: in expansion of macro 'rep'
155 | rep(i, 1, x.size() - 1) if (comp(i) != gfinal){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Runtime error |
1116 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Runtime error |
1116 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Runtime error |
1116 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Runtime error |
1116 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Runtime error |
1116 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Runtime error |
1116 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
