Submission #756016

#	Time	Username	Problem	Language	Result	Execution time	Memory
756016		thimote75	Robots (APIO13_robots)	C++14	100 / 100	849 ms	64560 KiB

robots

#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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40