Submission #435579

#	Time	Username	Problem	Language	Result	Execution time	Memory
435579		Ozy	Fountain Parks (IOI21_parks)	C++17	100 / 100	930 ms	55512 KiB

parks

#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;
int visitada[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, camino[6];
    int fuente[6];

    visitada[nodo] = 1;

    // VALIDA EN QUE DIRECCIONES TIENE FUENTE
    rep(i, norte, suroeste) camino[i] = false, 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){ // UNE SOLO AL NORTE
            if (une(nodo, fuente[norte])){
                u.push_back(nodo);
                v.push_back(fuente[norte]);
                a.push_back(x[nodo] - 1); // BANCA AL OESTE
                b.push_back((y[nodo] + y[fuente[norte]]) / 2);
                camino[norte] = true;
            }
        }
        else{ // UNE SOLO AL 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 SUR
                camino[este] = true;
            }
        }
    }
    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);
            camino[norte] = true;
        }
        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);
            camino[este] = true;
        }
    }

    // DESPUES DE UNIR, CONTINUA LA DFS A LAS FUENTES A LAS QUE CONSTRUISTE CAMINO
    rep(i, norte, este) if (hayfuente[i] && camino[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

    rep(i, 0, x.size() - 1) grupo[i] = i; // INICIALIZA EL DSU

    // VISITA TODAS LAS FUENTES UNIENDO SOLO HACIA EL NORTE Y AL ESTE
    rep(i, 0, x.size() - 1) if (!visitada[i]) dfs(i, -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 (stderr)

parks.cpp:129:5: warning: multi-line comment [-Wcomment]
  129 |     //      \| 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:118:5: note: in expansion of macro 'rep'
  118 |     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:136:5: note: in expansion of macro 'rep'
  136 |     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:139:5: note: in expansion of macro 'rep'
  139 |     rep(i, 0, x.size() - 1) if (!visitada[i]) dfs(i, -1, x, y);
      |     ^~~
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:144:5: note: in expansion of macro 'rep'
  144 |     rep(i, 1, x.size() - 1) if (comp(i) != gfinal){
      |     ^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30