oj.uz

Submission #435069

# Submission time Handle Problem Language Result Execution time Memory
435069 2021-06-22T22:27:42 Z ocarima Fountain Parks (IOI21_parks) C++17
5 / 100
 640 ms 77504 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;

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);
                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) 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:80:5: note: in expansion of macro 'rep'
   80 |     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:83:5: note: in expansion of macro 'rep'
   83 |     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:89:5: note: in expansion of macro 'rep'
   89 |     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 4904 KB Output is correct
6 Correct 3 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 214 ms 38588 KB Output is correct
10 Correct 20 ms 8652 KB Output is correct
11 Correct 106 ms 23744 KB Output is correct
12 Correct 30 ms 10464 KB Output is correct
13 Correct 56 ms 15740 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 219 ms 32296 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 4904 KB Output is correct
6 Correct 3 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 214 ms 38588 KB Output is correct
10 Correct 20 ms 8652 KB Output is correct
11 Correct 106 ms 23744 KB Output is correct
12 Correct 30 ms 10464 KB Output is correct
13 Correct 56 ms 15740 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 219 ms 32296 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 585 ms 77308 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 6 ms 5324 KB Output is correct
26 Correct 8 ms 5468 KB Output is correct
27 Correct 6 ms 5324 KB Output is correct
28 Correct 180 ms 33512 KB Output is correct
29 Incorrect 301 ms 43556 KB Tree @(3, 80003) appears more than once: for edges on positions 13943 and 13945
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 4904 KB Output is correct
6 Correct 3 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 214 ms 38588 KB Output is correct
10 Correct 20 ms 8652 KB Output is correct
11 Correct 106 ms 23744 KB Output is correct
12 Correct 30 ms 10464 KB Output is correct
13 Correct 56 ms 15740 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 219 ms 32296 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 585 ms 77308 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 6 ms 5324 KB Output is correct
26 Correct 8 ms 5468 KB Output is correct
27 Correct 6 ms 5324 KB Output is correct
28 Correct 180 ms 33512 KB Output is correct
29 Incorrect 301 ms 43556 KB Tree @(3, 80003) appears more than once: for edges on positions 13943 and 13945
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 4904 KB Output is correct
6 Correct 3 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 214 ms 38588 KB Output is correct
10 Correct 20 ms 8652 KB Output is correct
11 Correct 106 ms 23744 KB Output is correct
12 Correct 30 ms 10464 KB Output is correct
13 Correct 56 ms 15740 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 219 ms 32296 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 548 ms 74404 KB Output is correct
21 Correct 577 ms 68148 KB Output is correct
22 Correct 571 ms 64696 KB Output is correct
23 Correct 463 ms 54680 KB Output is correct
24 Correct 217 ms 21420 KB Output is correct
25 Correct 184 ms 21424 KB Output is correct
26 Correct 192 ms 21448 KB Output is correct
27 Incorrect 476 ms 43628 KB Tree @(1593, 3) appears more than once: for edges on positions 175095 and 175596
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 4904 KB Output is correct
6 Correct 3 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 214 ms 38588 KB Output is correct
10 Correct 20 ms 8652 KB Output is correct
11 Correct 106 ms 23744 KB Output is correct
12 Correct 30 ms 10464 KB Output is correct
13 Correct 56 ms 15740 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 219 ms 32296 KB Output is correct
17 Correct 611 ms 77364 KB Output is correct
18 Correct 611 ms 72992 KB Output is correct
19 Correct 602 ms 77504 KB Output is correct
20 Incorrect 640 ms 63128 KB Tree @(7, 5) appears more than once: for edges on positions 19235 and 19236
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 4904 KB Output is correct
6 Correct 3 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 214 ms 38588 KB Output is correct
10 Correct 20 ms 8652 KB Output is correct
11 Correct 106 ms 23744 KB Output is correct
12 Correct 30 ms 10464 KB Output is correct
13 Correct 56 ms 15740 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 219 ms 32296 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 585 ms 77308 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 6 ms 5324 KB Output is correct
26 Correct 8 ms 5468 KB Output is correct
27 Correct 6 ms 5324 KB Output is correct
28 Correct 180 ms 33512 KB Output is correct
29 Incorrect 301 ms 43556 KB Tree @(3, 80003) appears more than once: for edges on positions 13943 and 13945
30 Halted 0 ms 0 KB -