oj.uz

Submission #435553

# Submission time Handle Problem Language Result Execution time Memory
435553 2021-06-23T12:29:31 Z ocarima Fountain Parks (IOI21_parks) C++17
45 / 100
 611 ms 67604 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[oeste]]) / 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 5 ms 4940 KB Output is correct
3 Correct 4 ms 4920 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 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 211 ms 33844 KB Output is correct
10 Correct 21 ms 8140 KB Output is correct
11 Correct 108 ms 21308 KB Output is correct
12 Correct 36 ms 9688 KB Output is correct
13 Correct 57 ms 14472 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 190 ms 26864 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 5 ms 4940 KB Output is correct
3 Correct 4 ms 4920 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 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 211 ms 33844 KB Output is correct
10 Correct 21 ms 8140 KB Output is correct
11 Correct 108 ms 21308 KB Output is correct
12 Correct 36 ms 9688 KB Output is correct
13 Correct 57 ms 14472 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 190 ms 26864 KB Output is correct
17 Incorrect 3 ms 4940 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
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 5 ms 4940 KB Output is correct
3 Correct 4 ms 4920 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 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 211 ms 33844 KB Output is correct
10 Correct 21 ms 8140 KB Output is correct
11 Correct 108 ms 21308 KB Output is correct
12 Correct 36 ms 9688 KB Output is correct
13 Correct 57 ms 14472 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 190 ms 26864 KB Output is correct
17 Incorrect 3 ms 4940 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 4 ms 4920 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 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 211 ms 33844 KB Output is correct
10 Correct 21 ms 8140 KB Output is correct
11 Correct 108 ms 21308 KB Output is correct
12 Correct 36 ms 9688 KB Output is correct
13 Correct 57 ms 14472 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 190 ms 26864 KB Output is correct
17 Correct 5 ms 4940 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 4 ms 4940 KB Output is correct
20 Correct 559 ms 65040 KB Output is correct
21 Correct 611 ms 58212 KB Output is correct
22 Correct 537 ms 54376 KB Output is correct
23 Correct 413 ms 45804 KB Output is correct
24 Correct 219 ms 21316 KB Output is correct
25 Correct 202 ms 21572 KB Output is correct
26 Correct 240 ms 21404 KB Output is correct
27 Correct 464 ms 32312 KB Output is correct
28 Correct 424 ms 31196 KB Output is correct
29 Correct 608 ms 31180 KB Output is correct
30 Correct 604 ms 31232 KB Output is correct
31 Correct 4 ms 4956 KB Output is correct
32 Correct 33 ms 8152 KB Output is correct
33 Correct 82 ms 13096 KB Output is correct
34 Correct 517 ms 59596 KB Output is correct
35 Correct 13 ms 5964 KB Output is correct
36 Correct 57 ms 9304 KB Output is correct
37 Correct 100 ms 13460 KB Output is correct
38 Correct 169 ms 15740 KB Output is correct
39 Correct 261 ms 19516 KB Output is correct
40 Correct 344 ms 23716 KB Output is correct
41 Correct 451 ms 27816 KB Output is correct
42 Correct 598 ms 31944 KB Output is correct
43 Correct 4 ms 4940 KB Output is correct
44 Correct 5 ms 4940 KB Output is correct
45 Correct 4 ms 4896 KB Output is correct
46 Correct 5 ms 4940 KB Output is correct
47 Correct 4 ms 4940 KB Output is correct
48 Correct 4 ms 4876 KB Output is correct
49 Correct 4 ms 4940 KB Output is correct
50 Correct 4 ms 4940 KB Output is correct
51 Correct 4 ms 4940 KB Output is correct
52 Correct 4 ms 4940 KB Output is correct
53 Correct 4 ms 4940 KB Output is correct
54 Correct 6 ms 5196 KB Output is correct
55 Correct 6 ms 5324 KB Output is correct
56 Correct 206 ms 28656 KB Output is correct
57 Correct 385 ms 40344 KB Output is correct
58 Correct 339 ms 39200 KB Output is correct
59 Correct 5 ms 4940 KB Output is correct
60 Correct 4 ms 4940 KB Output is correct
61 Correct 5 ms 4940 KB Output is correct
62 Correct 450 ms 55544 KB Output is correct
63 Correct 467 ms 56004 KB Output is correct
64 Correct 450 ms 59520 KB Output is correct
65 Correct 9 ms 5452 KB Output is correct
66 Correct 10 ms 5836 KB Output is correct
67 Correct 218 ms 23724 KB Output is correct
68 Correct 405 ms 37448 KB Output is correct
69 Correct 575 ms 42908 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 4 ms 4920 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 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 211 ms 33844 KB Output is correct
10 Correct 21 ms 8140 KB Output is correct
11 Correct 108 ms 21308 KB Output is correct
12 Correct 36 ms 9688 KB Output is correct
13 Correct 57 ms 14472 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 190 ms 26864 KB Output is correct
17 Correct 546 ms 67336 KB Output is correct
18 Correct 495 ms 63100 KB Output is correct
19 Correct 500 ms 67604 KB Output is correct
20 Correct 553 ms 52916 KB Output is correct
21 Correct 444 ms 44536 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 64 ms 10928 KB Output is correct
24 Correct 26 ms 7588 KB Output is correct
25 Correct 91 ms 11948 KB Output is correct
26 Correct 138 ms 16072 KB Output is correct
27 Correct 254 ms 26380 KB Output is correct
28 Correct 341 ms 32796 KB Output is correct
29 Correct 423 ms 38096 KB Output is correct
30 Correct 529 ms 42944 KB Output is correct
31 Correct 608 ms 49332 KB Output is correct
32 Correct 540 ms 58412 KB Output is correct
33 Correct 513 ms 67368 KB Output is correct
34 Correct 8 ms 5708 KB Output is correct
35 Correct 11 ms 6092 KB Output is correct
36 Correct 259 ms 24976 KB Output is correct
37 Correct 400 ms 35760 KB Output is correct
38 Correct 576 ms 46316 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 4 ms 4920 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 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 211 ms 33844 KB Output is correct
10 Correct 21 ms 8140 KB Output is correct
11 Correct 108 ms 21308 KB Output is correct
12 Correct 36 ms 9688 KB Output is correct
13 Correct 57 ms 14472 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 190 ms 26864 KB Output is correct
17 Incorrect 3 ms 4940 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -