oj.uz

Submission #435070

# Submission time Handle Problem Language Result Execution time Memory
435070 2021-06-22T22:30:55 Z ocarima Fountain Parks (IOI21_parks) C++17
5 / 100
 670 ms 77452 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, int direccion, vector<int> &x, vector<int> &y){

    rep(i, 0, 3){
        if (fuentes.find({x[nodo] + dx[(direccion + i) & 3], y[nodo] + dy[(direccion + i) & 3]}) != fuentes.end()){ // EXISTE FUENTE EN ESA DIRECCION
            int h = fuentes[{x[nodo] + dx[(direccion + i) & 3], y[nodo] + dy[(direccion + i) & 3]}];
            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;

                int dirhijo = (direccion + i + 2) & 3; // Norte se vuelve sur, este oeste, etc.
                dfs(h, nodo, dirhijo, 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, 0, 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:87:5: note: in expansion of macro 'rep'
   87 |     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:90:5: note: in expansion of macro 'rep'
   90 |     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:96:5: note: in expansion of macro 'rep'
   96 |     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 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 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 261 ms 38584 KB Output is correct
10 Correct 24 ms 8572 KB Output is correct
11 Correct 115 ms 23768 KB Output is correct
12 Correct 31 ms 10440 KB Output is correct
13 Correct 78 ms 15684 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 233 ms 32216 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 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 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 261 ms 38584 KB Output is correct
10 Correct 24 ms 8572 KB Output is correct
11 Correct 115 ms 23768 KB Output is correct
12 Correct 31 ms 10440 KB Output is correct
13 Correct 78 ms 15684 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 233 ms 32216 KB Output is correct
17 Correct 4 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 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 632 ms 77292 KB Output is correct
24 Correct 4 ms 4940 KB Output is correct
25 Correct 6 ms 5324 KB Output is correct
26 Correct 6 ms 5452 KB Output is correct
27 Correct 6 ms 5324 KB Output is correct
28 Correct 198 ms 33616 KB Output is correct
29 Incorrect 256 ms 38940 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 4 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 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 261 ms 38584 KB Output is correct
10 Correct 24 ms 8572 KB Output is correct
11 Correct 115 ms 23768 KB Output is correct
12 Correct 31 ms 10440 KB Output is correct
13 Correct 78 ms 15684 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 233 ms 32216 KB Output is correct
17 Correct 4 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 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 632 ms 77292 KB Output is correct
24 Correct 4 ms 4940 KB Output is correct
25 Correct 6 ms 5324 KB Output is correct
26 Correct 6 ms 5452 KB Output is correct
27 Correct 6 ms 5324 KB Output is correct
28 Correct 198 ms 33616 KB Output is correct
29 Incorrect 256 ms 38940 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 4 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 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 261 ms 38584 KB Output is correct
10 Correct 24 ms 8572 KB Output is correct
11 Correct 115 ms 23768 KB Output is correct
12 Correct 31 ms 10440 KB Output is correct
13 Correct 78 ms 15684 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 233 ms 32216 KB Output is correct
17 Correct 3 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 625 ms 74368 KB Output is correct
21 Correct 670 ms 68160 KB Output is correct
22 Correct 620 ms 64592 KB Output is correct
23 Correct 598 ms 54608 KB Output is correct
24 Correct 252 ms 21420 KB Output is correct
25 Correct 181 ms 21400 KB Output is correct
26 Correct 190 ms 21576 KB Output is correct
27 Incorrect 383 ms 35448 KB Solution announced impossible, but it is possible.
28 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 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 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 261 ms 38584 KB Output is correct
10 Correct 24 ms 8572 KB Output is correct
11 Correct 115 ms 23768 KB Output is correct
12 Correct 31 ms 10440 KB Output is correct
13 Correct 78 ms 15684 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 233 ms 32216 KB Output is correct
17 Correct 588 ms 77296 KB Output is correct
18 Correct 580 ms 72956 KB Output is correct
19 Correct 589 ms 77452 KB Output is correct
20 Incorrect 384 ms 34888 KB Solution announced impossible, but it is possible.
21 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 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 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 261 ms 38584 KB Output is correct
10 Correct 24 ms 8572 KB Output is correct
11 Correct 115 ms 23768 KB Output is correct
12 Correct 31 ms 10440 KB Output is correct
13 Correct 78 ms 15684 KB Output is correct
14 Correct 5 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 233 ms 32216 KB Output is correct
17 Correct 4 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 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 632 ms 77292 KB Output is correct
24 Correct 4 ms 4940 KB Output is correct
25 Correct 6 ms 5324 KB Output is correct
26 Correct 6 ms 5452 KB Output is correct
27 Correct 6 ms 5324 KB Output is correct
28 Correct 198 ms 33616 KB Output is correct
29 Incorrect 256 ms 38940 KB Solution announced impossible, but it is possible.
30 Halted 0 ms 0 KB -