Submission #246985

#	Time	Username	Problem	Language	Result	Execution time	Memory
246985		keko37	Robots (APIO13_robots)	C++14	60 / 100	1583 ms	84084 KiB

robots

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 505;

int n, h, w, sol = 1e9;
int robot[20];
char a[MAXN][MAXN];
pi nxt[MAXN*MAXN][4];
int to[MAXN*MAXN][4], bio[MAXN * MAXN];
int dist[MAXN * MAXN][10][10];
vector <int> v;
set <pi> st;
queue <int> q;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool ok (int x, int y) {
    return 0 <= x && x < h && 0 <= y && y < w;
}

void build_succesor () {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (a[i][j] == 'x') continue;
            for (int d = 0; d < 4; d++) {
                int nx, ny, nd;
                nd = (a[i][j] == 'A' ? (d + 3) % 4 : (a[i][j] == 'C' ? (d + 1) % 4 : d));
                nx = i + dx[nd];
                ny = j + dy[nd];
                if (!ok(nx, ny) || a[nx][ny] == 'x') {
                    nxt[i*w+j][d] = {i*w+j, -1};
                } else {
                    nxt[i*w+j][d] = {nx*w+ny, nd};
                }
            }
        }
    }
}

int get_sink (int node, int d) {
    if (to[node][d] >= 0) return to[node][d];
    to[node][d] = -2;
    if (nxt[node][d].second == -1) {
        return to[node][d] = nxt[node][d].first;
    } else {
        int succ = nxt[node][d].first, nd = nxt[node][d].second;
        if (to[succ][nd] == -2) {
            return to[node][d] = -3;
        } else {
            return to[node][d] = get_sink(succ, nd);
        }
    }
}

void build_graph () {
    memset(to, -1, sizeof to);
    for (int i = 0; i < n; i++) {
        q.push(robot[i]);
        bio[robot[i]] = 1;
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        v.push_back(x);
        for (int d = 0; d < 4; d++) {
            int sus = get_sink(x, d);
            if (!bio[sus]) {
                q.push(sus);
                bio[sus] = 1;
            }
        }
    }
}
void solve (int lo, int hi) {
    st.clear();
    for (auto x : v) dist[x][lo][hi] = 1e9;
    if (lo == hi) {
        dist[robot[lo]][lo][lo] = 0;
        st.insert({0, robot[lo]});
    } else {
        for (auto x : v) {
            for (int i = lo; i < hi; i++) {
                int val = dist[x][lo][i] + dist[x][i + 1][hi];
                dist[x][lo][hi] = min(dist[x][lo][hi], val);
            }
            if (dist[x][lo][hi] < 1e9) st.insert({dist[x][lo][hi], x});
        }
    }
    while (!st.empty()) {
        int x = st.begin() -> second;
        int len = st.begin() -> first;
        st.erase(st.begin());
        for (int d = 0; d < 4; d++) {
            int sus = to[x][d];
            if (sus < 0) continue;
            if (len + 1 < dist[sus][lo][hi]) {
                if (st.find({dist[sus][lo][hi], sus}) != st.end()) st.erase({dist[sus][lo][hi], sus});
                dist[sus][lo][hi] = len + 1;
                st.insert({dist[sus][lo][hi], sus});
            }
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> w >> h;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
            if ('1' <= a[i][j] && a[i][j] <= '9') {
                robot[a[i][j] - '1'] = i*w+j;
            }
        }
    }
    build_succesor();
    build_graph();
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            solve(i, i + len - 1);
        }
    }
    for (auto x : v) sol = min(sol, dist[x][0][n - 1]);
    if (sol == 1e9) cout << -1; else cout << sol;
    return 0;
}

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