oj.uz

Submission #435060

# Submission time Handle Problem Language Result Execution time Memory
435060 2021-06-22T22:01:58 Z ocarima Fountain Parks (IOI21_parks) C++17
0 / 100
 5 ms 4940 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];
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]}] - 1;
                hijos[i].push_back(destino);
                hijos[destino].push_back(i);
            }
        }
        fuentes[{x[i], y[i]}] = i + 1; // 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()) grupo[i] = i; // INICIALIZA EL DSU
    dfs(0, -1, x, y);



    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()) grupo[i] = i; // INICIALIZA EL DSU
      |     ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Incorrect 3 ms 4940 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Incorrect 3 ms 4940 KB Given structure is not connected: There is no path between vertices 0 and 1
4 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 5 ms 4940 KB Output is correct
3 Incorrect 3 ms 4940 KB Given structure is not connected: There is no path between vertices 0 and 1
4 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 5 ms 4940 KB Output is correct
3 Incorrect 3 ms 4940 KB Given structure is not connected: There is no path between vertices 0 and 1
4 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 5 ms 4940 KB Output is correct
3 Incorrect 3 ms 4940 KB Given structure is not connected: There is no path between vertices 0 and 1
4 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 5 ms 4940 KB Output is correct
3 Incorrect 3 ms 4940 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -