oj.uz

Submission #435549

# Submission time Handle Problem Language Result Execution time Memory
435549 2021-06-23T12:27:07 Z ocarima Fountain Parks (IOI21_parks) C++17
5 / 100
 482 ms 67344 KB 
#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, camino[6];
    int fuente[6];

    // 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){ // 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
                camino[este] = true;
            }
        }
        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);
                camino[norte] = 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;
        }
    }

    // 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);
        camino[oeste] = true;
    }
    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);
        camino[sur] = 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, 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:146:5: warning: multi-line comment [-Wcomment]
  146 |     //      \| 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:135:5: note: in expansion of macro 'rep'
  135 |     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:154:5: note: in expansion of macro 'rep'
  154 |     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:160:5: note: in expansion of macro 'rep'
  160 |     rep(i, 1, x.size() - 1) if (comp(i) != gfinal){
      |     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 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 4 ms 4940 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 186 ms 33836 KB Output is correct
10 Correct 22 ms 8164 KB Output is correct
11 Correct 99 ms 21288 KB Output is correct
12 Correct 32 ms 9664 KB Output is correct
13 Correct 52 ms 14532 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 187 ms 26880 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 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 4 ms 4940 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 186 ms 33836 KB Output is correct
10 Correct 22 ms 8164 KB Output is correct
11 Correct 99 ms 21288 KB Output is correct
12 Correct 32 ms 9664 KB Output is correct
13 Correct 52 ms 14532 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 187 ms 26880 KB Output is correct
17 Incorrect 5 ms 4940 KB a[0] = 2 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 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 4 ms 4940 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 186 ms 33836 KB Output is correct
10 Correct 22 ms 8164 KB Output is correct
11 Correct 99 ms 21288 KB Output is correct
12 Correct 32 ms 9664 KB Output is correct
13 Correct 52 ms 14532 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 187 ms 26880 KB Output is correct
17 Incorrect 5 ms 4940 KB a[0] = 2 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 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 4 ms 4940 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 186 ms 33836 KB Output is correct
10 Correct 22 ms 8164 KB Output is correct
11 Correct 99 ms 21288 KB Output is correct
12 Correct 32 ms 9664 KB Output is correct
13 Correct 52 ms 14532 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 187 ms 26880 KB Output is correct
17 Incorrect 4 ms 4940 KB a[1] = 200000 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 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 4 ms 4940 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 186 ms 33836 KB Output is correct
10 Correct 22 ms 8164 KB Output is correct
11 Correct 99 ms 21288 KB Output is correct
12 Correct 32 ms 9664 KB Output is correct
13 Correct 52 ms 14532 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 187 ms 26880 KB Output is correct
17 Incorrect 482 ms 67344 KB Tree (a[1], b[1]) = (41211, 100003) is not adjacent to edge between u[1]=0 @(82422, 100002) and v[1]=148989 @(82420, 100002)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 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 4 ms 4940 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 186 ms 33836 KB Output is correct
10 Correct 22 ms 8164 KB Output is correct
11 Correct 99 ms 21288 KB Output is correct
12 Correct 32 ms 9664 KB Output is correct
13 Correct 52 ms 14532 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 187 ms 26880 KB Output is correct
17 Incorrect 5 ms 4940 KB a[0] = 2 is not an odd integer
18 Halted 0 ms 0 KB -