Submission #246999

#	Time	Username	Problem	Language	Result	Execution time	Memory
246999		keko37	Robots (APIO13_robots)	C++14	100 / 100	1144 ms	89032 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, r[MAXN * MAXN];
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) {
    for (auto x : v) dist[x][lo][hi] = 1e9;
    int mn = 1e9;
    if (lo == hi) {
        dist[robot[lo]][lo][lo] = 0;
        mn = 0;
    } 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);
            }
            mn = min(mn, dist[x][lo][hi]);
        }
    }
    for (auto x : v) {
        bio[x] = 0;
        int val = dist[x][lo][hi] - mn;
        if (val < v.size()) r[val].push_back(x);
    }
    for (int i = 0; i < v.size(); i++) {
        while (!r[i].empty()) {
            int x = r[i].back();
            r[i].pop_back();
            if (!bio[x]) {
                q.push(x);
                bio[x] = 1;
            }
        }
        while (!q.empty()) {
            int x = q.front(), len = dist[x][lo][hi];
            if (len != mn + i) break;
            q.pop();
            for (int d = 0; d < 4; d++) {
                int sus = to[x][d];
                if (sus >= 0 && !bio[sus]) {
                    q.push(sus);
                    bio[sus] = 1;
                    dist[sus][lo][hi] = len + 1;
                }
            }
        }
    }
}

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;
}

Compilation message (stderr)

robots.cpp: In function 'void solve(int, int)':
robots.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (val < v.size()) r[val].push_back(x);
             ~~~~^~~~~~~~~~
robots.cpp:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++) {
                     ~~^~~~~~~~~~

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