oj.uz

Submission #246999

# Submission time Handle Problem Language Result Execution time Memory
246999 2020-07-10T17:27:46 Z keko37 Robots (APIO13_robots) C++14
100 / 100
 1144 ms 89032 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10368 KB Output is correct
2 Correct 11 ms 10368 KB Output is correct
3 Correct 11 ms 10368 KB Output is correct
4 Correct 10 ms 10368 KB Output is correct
5 Correct 10 ms 10368 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10368 KB Output is correct
2 Correct 11 ms 10368 KB Output is correct
3 Correct 11 ms 10368 KB Output is correct
4 Correct 10 ms 10368 KB Output is correct
5 Correct 10 ms 10368 KB Output is correct
6 Correct 10 ms 10368 KB Output is correct
7 Correct 10 ms 10368 KB Output is correct
8 Correct 10 ms 10368 KB Output is correct
9 Correct 10 ms 10368 KB Output is correct
10 Correct 10 ms 10368 KB Output is correct
11 Correct 153 ms 37112 KB Output is correct
12 Correct 27 ms 36472 KB Output is correct
13 Correct 18 ms 13568 KB Output is correct
14 Correct 330 ms 38136 KB Output is correct
15 Correct 182 ms 37240 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10368 KB Output is correct
2 Correct 11 ms 10368 KB Output is correct
3 Correct 11 ms 10368 KB Output is correct
4 Correct 10 ms 10368 KB Output is correct
5 Correct 10 ms 10368 KB Output is correct
6 Correct 10 ms 10368 KB Output is correct
7 Correct 10 ms 10368 KB Output is correct
8 Correct 10 ms 10368 KB Output is correct
9 Correct 10 ms 10368 KB Output is correct
10 Correct 10 ms 10368 KB Output is correct
11 Correct 153 ms 37112 KB Output is correct
12 Correct 27 ms 36472 KB Output is correct
13 Correct 18 ms 13568 KB Output is correct
14 Correct 330 ms 38136 KB Output is correct
15 Correct 182 ms 37240 KB Output is correct
16 Correct 28 ms 21632 KB Output is correct
17 Correct 1144 ms 89032 KB Output is correct
18 Correct 707 ms 86004 KB Output is correct
19 Correct 37 ms 19064 KB Output is correct
20 Correct 771 ms 85620 KB Output is correct