oj.uz

Submission #435065

# Submission time Handle Problem Language Result Execution time Memory
435065 2021-06-22T22:07:48 Z ocarima Fountain Parks (IOI21_parks) C++17
5 / 100
 894 ms 83788 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] = {2, 0, -2, 0};
int dy[4] = {0, 2, 0, -2};

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;

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){
    for(auto h : hijos[nodo]){
        if (h == padre) continue;
        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);
            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;
    }

    // ES NECESARIO CONSTRUIR UN GRAFO PARA SABER QUE FUENTES PUEDEN IR UNIDAS CON QUE FUENTES, COMO CADA FUENTE SOLO PUEDE IR UNIDA A 4, ENTONCES USAREMOS UN MAP
    int destino;
    rep(i, 0, x.size() - 1){
        rep(j, 0, 3){
            if (fuentes.find({x[i] + dx[j], y[i] + dy[j]}) != fuentes.end()){
                destino = fuentes[{x[i] + dx[j], y[i] + dy[j]}];
                hijos[i].push_back(destino);
                hijos[destino].push_back(i);
            }
        }
        fuentes[{x[i], y[i]}] = i; // AGREGA ESTA FUENTE AL MAPA
    }

    // 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) 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:77:5: note: in expansion of macro 'rep'
   77 |     rep(i, 0, x.size() - 1){
      |     ^~~
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 4 ms 4940 KB Output is correct
4 Correct 3 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 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 285 ms 41632 KB Output is correct
10 Correct 20 ms 8908 KB Output is correct
11 Correct 115 ms 25440 KB Output is correct
12 Correct 29 ms 10976 KB Output is correct
13 Correct 62 ms 17132 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5324 KB Output is correct
16 Correct 288 ms 35376 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 4 ms 4940 KB Output is correct
4 Correct 3 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 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 285 ms 41632 KB Output is correct
10 Correct 20 ms 8908 KB Output is correct
11 Correct 115 ms 25440 KB Output is correct
12 Correct 29 ms 10976 KB Output is correct
13 Correct 62 ms 17132 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5324 KB Output is correct
16 Correct 288 ms 35376 KB Output is correct
17 Correct 4 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 3 ms 4968 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 870 ms 71700 KB Output is correct
24 Correct 4 ms 4940 KB Output is correct
25 Correct 6 ms 5324 KB Output is correct
26 Correct 7 ms 5452 KB Output is correct
27 Correct 8 ms 5508 KB Output is correct
28 Correct 250 ms 32544 KB Output is correct
29 Incorrect 423 ms 42048 KB Tree @(3, 80003) appears more than once: for edges on positions 23837 and 23839
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 4 ms 4940 KB Output is correct
4 Correct 3 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 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 285 ms 41632 KB Output is correct
10 Correct 20 ms 8908 KB Output is correct
11 Correct 115 ms 25440 KB Output is correct
12 Correct 29 ms 10976 KB Output is correct
13 Correct 62 ms 17132 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5324 KB Output is correct
16 Correct 288 ms 35376 KB Output is correct
17 Correct 4 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 3 ms 4968 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 870 ms 71700 KB Output is correct
24 Correct 4 ms 4940 KB Output is correct
25 Correct 6 ms 5324 KB Output is correct
26 Correct 7 ms 5452 KB Output is correct
27 Correct 8 ms 5508 KB Output is correct
28 Correct 250 ms 32544 KB Output is correct
29 Incorrect 423 ms 42048 KB Tree @(3, 80003) appears more than once: for edges on positions 23837 and 23839
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 4 ms 4940 KB Output is correct
4 Correct 3 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 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 285 ms 41632 KB Output is correct
10 Correct 20 ms 8908 KB Output is correct
11 Correct 115 ms 25440 KB Output is correct
12 Correct 29 ms 10976 KB Output is correct
13 Correct 62 ms 17132 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5324 KB Output is correct
16 Correct 288 ms 35376 KB Output is correct
17 Correct 4 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 764 ms 80676 KB Output is correct
21 Correct 802 ms 74532 KB Output is correct
22 Correct 790 ms 70852 KB Output is correct
23 Correct 595 ms 60040 KB Output is correct
24 Correct 358 ms 21316 KB Output is correct
25 Correct 554 ms 27660 KB Output is correct
26 Correct 503 ms 27828 KB Output is correct
27 Incorrect 741 ms 49848 KB Tree @(1593, 3) appears more than once: for edges on positions 4579 and 5080
28 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 4 ms 4940 KB Output is correct
4 Correct 3 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 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 285 ms 41632 KB Output is correct
10 Correct 20 ms 8908 KB Output is correct
11 Correct 115 ms 25440 KB Output is correct
12 Correct 29 ms 10976 KB Output is correct
13 Correct 62 ms 17132 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5324 KB Output is correct
16 Correct 288 ms 35376 KB Output is correct
17 Correct 709 ms 83556 KB Output is correct
18 Correct 747 ms 79300 KB Output is correct
19 Correct 809 ms 83788 KB Output is correct
20 Incorrect 894 ms 60288 KB Tree @(507, 893) appears more than once: for edges on positions 266 and 268
21 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 4 ms 4940 KB Output is correct
4 Correct 3 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 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 285 ms 41632 KB Output is correct
10 Correct 20 ms 8908 KB Output is correct
11 Correct 115 ms 25440 KB Output is correct
12 Correct 29 ms 10976 KB Output is correct
13 Correct 62 ms 17132 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5324 KB Output is correct
16 Correct 288 ms 35376 KB Output is correct
17 Correct 4 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 3 ms 4968 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 870 ms 71700 KB Output is correct
24 Correct 4 ms 4940 KB Output is correct
25 Correct 6 ms 5324 KB Output is correct
26 Correct 7 ms 5452 KB Output is correct
27 Correct 8 ms 5508 KB Output is correct
28 Correct 250 ms 32544 KB Output is correct
29 Incorrect 423 ms 42048 KB Tree @(3, 80003) appears more than once: for edges on positions 23837 and 23839
30 Halted 0 ms 0 KB -