oj.uz

Submission #756016

# Submission time Handle Problem Language Result Execution time Memory
756016 2023-06-10T21:35:49 Z thimote75 Robots (APIO13_robots) C++14
100 / 100
 849 ms 64560 KB 
#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;

template<typename T>
using  grid = vector<vector<T>>;
using igrid = grid<int>;
using bgrid = grid<bool>;

using pos = pair<int, int>;
using graph = grid<vector<pos>>;

using vpos = vector<pos>;
using dist_pos = pair<int, pos>;
using dist_pqp = priority_queue<dist_pos, vector<dist_pos>, less<dist_pos>>;

const int WALL    = 0;
const int EMPTY   = 1;
const int WHEEL_C = 2; // clockwise
const int WHEEL_A = 3; // counter clockwise

const int INF = 1e9;

template<typename T>
void resize (grid<T> &data_grid, int width, int height, T def) {
    data_grid.resize(width, vector<T>(height, def));
}
template<typename T>
T get (grid<T> &data, pos pos) {
    return data[pos.first][pos.second];
}

template<typename T>
void show (T &o) {
    cout << o;
}
void show (int &x) {
    if (x == INF) cout << "-";
    else cout << x;
}
template<typename U, typename V>
void show (pair<U, V> &p) {
    cout << "(";
    show(p.first);
    cout << ", ";
    show(p.second);
    cout << ")";
}
template<typename T>
void show(vector<T> &vector) {
    cout << "[";
    for (T u : vector) {
        show(u);
        cout << ", ";
    }
    cout << "]";
}
template<typename T>
void show(grid<T> &data_grid, int width, int height) {
    for (int y = 0; y < height; y ++) {
        for (int x = 0; x < width; x ++)
            show(data_grid[x][y]);
        cout << endl;
    }
}

int nbRobots, width, height;
igrid type_grid;
graph roads;

bool is_valid (pos node) {
    int x = node.first;
    int y = node.second;

    return 0 <= x && x < width
        && 0 <= y && y < height;
}
pos get_next (pos node, int direction) {
    int x = node.first;
    int y = node.second;

    if (direction == 0) return { x + 1, y };
    if (direction == 1) return { x, y - 1 };
    if (direction == 2) return { x - 1, y };
    if (direction == 3) return { x, y + 1 };

    return node;
}
void dfs (pos start, pos node, int direction) {
    int type = get(type_grid, node);
    if (type == WALL) return ;
    if (type == WHEEL_A) direction --;
    if (type == WHEEL_C) direction ++;

    if (direction  < 0) direction += 4;
    if (direction == 4) direction  = 0;

    pos next = get_next(node, direction);

    if (node.first != start.first || node.second != start.second)
        roads[node.first][node.second].push_back(start);

    if (!is_valid(next)) return ;

    dfs(start, next, direction);
}
void create   (igrid &grid, pos start) {
    resize(grid, width, height, INF);

    if (start.first == -1 && start.second == -1) return ;
    grid[start.first][start.second] = 0;
}
void dijkstra (igrid &grid) {
    vector<dist_pos> p_queue;
    queue<dist_pos> normal_queue;
    
    for (int y = 0; y < height; y ++) {
        for (int x = 0; x < width; x ++) {
            if (grid[x][y] == INF) continue ;

            p_queue.push_back({ grid[x][y], { x, y } });
        }
    }

    sort(p_queue.begin(), p_queue.end());
    reverse(p_queue.begin(), p_queue.end());

    while (normal_queue.size() != 0 || p_queue.size() != 0) {
        dist_pos curr;
        if (normal_queue.size() == 0) {
            curr = p_queue.back();
            p_queue.pop_back();
        } else if (p_queue.size() == 0) {
            curr = normal_queue.front();
            normal_queue.pop();
        } else if (p_queue.back() < normal_queue.front()) {
            curr = p_queue.back();
            p_queue.pop_back();
        } else {
            curr = normal_queue.front();
            normal_queue.pop();
        }

        pos rpos = curr.second;
        int cost = curr.first;

        if (grid[rpos.first][rpos.second] != cost) continue ;

        cost ++;

        for (pos next : roads[rpos.first][rpos.second]) {
            if (grid[next.first][next.second] <= cost) continue ;

            grid[next.first][next.second] = cost;
            normal_queue.push({ cost, next });
        }
    }
}
void merge (vpos &usable_pos, igrid &a, igrid &b, igrid &target) {
    for (pos p : usable_pos) {
        int x = p.first; int y = p.second;

        target[x][y] = min(
            target[x][y],
            a[x][y] + b[x][y]
        );
    }
}

using namespace std::chrono;
vector<vector<igrid>> grids;

int main () {
    cin >> nbRobots >> width >> height;

    resize(type_grid, width, height, -1);
    resize(roads, width, height, vector<pos>());

    vector<pos> robots(nbRobots);

    for (int y = 0; y < height; y ++) {
        string buffer;
        cin >> buffer;

        for (int x = 0; x < width; x ++) {
            char c = buffer[x];

            int type = EMPTY;
            if (c == 'x') type = WALL;
            else if (c == 'A') type = WHEEL_A;
            else if (c == 'C') type = WHEEL_C;
            else if (c != '.') {
                int robot_id = (int) (c - '1');

                robots[robot_id] = { x, y };
            }

            type_grid[x][y] = type;
        }
    }

    int i = 0;
    for (int y = 0; y < height; y ++) {
        for (int x = 0; x < width; x ++) {
            for (int dir = 0; dir < 4; dir ++) {
                int opp = (2 + dir) % 4;

                pos node = { x, y };
                pos wall = get_next(node, opp);
                bool is_wall = (!is_valid(wall)) || (get(type_grid, wall) == WALL);

                if (!is_wall) continue ;

                dfs(node, node, dir);
            }
        }
    }

    grids.resize(nbRobots);

    bgrid usable;
    resize(usable, width, height, false);

    vpos usable_pos;

    for (int iR = 0; iR < nbRobots; iR ++) {
        grids[iR].resize(nbRobots - iR);

        create(grids[iR][0], robots[iR]);
        dijkstra(grids[iR][0]);

        for (int y = 0; y < height; y ++) {
            for (int x = 0; x < width; x ++) {
                if (grids[iR][0][x][y] == INF || usable[x][y]) continue ;

                usable[x][y] = true;
                usable_pos.push_back({ x, y });
            }
        }
    }

    for (int size = 1; size < nbRobots; size ++) {
        for (int iR = 0; iR + size < nbRobots; iR ++) {
            create(grids[iR][size], { -1, -1 });

            for (int pivot_size = 0; pivot_size < size; pivot_size ++) {
                int other_size = size - 1 - pivot_size;
                
                merge( usable_pos, grids[iR][pivot_size], grids[iR + pivot_size + 1][other_size], grids[iR][size] );
            }

            dijkstra(grids[iR][size]);
        }
    }

    igrid &last_grid = grids[0][nbRobots - 1];

    int min_value = INF;
    for (int y = 0; y < height; y ++) {
        for (int x = 0; x < width; x ++) {
            min_value = min(min_value, last_grid[x][y]);
        }
    }

    if (min_value == INF) min_value = -1;
    cout << min_value << endl;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:205:9: warning: unused variable 'i' [-Wunused-variable]
  205 |     int i = 0;
      |         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 97 ms 20644 KB Output is correct
12 Correct 13 ms 4948 KB Output is correct
13 Correct 20 ms 14520 KB Output is correct
14 Correct 271 ms 21716 KB Output is correct
15 Correct 74 ms 20388 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 97 ms 20644 KB Output is correct
12 Correct 13 ms 4948 KB Output is correct
13 Correct 20 ms 14520 KB Output is correct
14 Correct 271 ms 21716 KB Output is correct
15 Correct 74 ms 20388 KB Output is correct
16 Correct 118 ms 64560 KB Output is correct
17 Correct 849 ms 59812 KB Output is correct
18 Correct 184 ms 56460 KB Output is correct
19 Correct 69 ms 56304 KB Output is correct
20 Correct 527 ms 58884 KB Output is correct