oj.uz

Submission #435075

# Submission time Handle Problem Language Result Execution time Memory
435075 2021-06-22T22:39:39 Z ocarima Fountain Parks (IOI21_parks) C++17
5 / 100
 657 ms 77288 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[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){
      |     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory 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

Subtask #2
0 / 10.0

# Verdict Execution time Memory 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 -

Subtask #3
0 / 15.0

# Verdict Execution time Memory 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 -

Subtask #4
0 / 20.0

# Verdict Execution time Memory 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 -

Subtask #5
0 / 20.0

# Verdict Execution time Memory 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 -

Subtask #6
0 / 30.0

# Verdict Execution time Memory 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 -