oj.uz

Submission #477934

# Submission time Handle Problem Language Result Execution time Memory
477934 2021-10-04T16:27:35 Z jungsnow Robots (APIO13_robots) C++14
100 / 100
 877 ms 111416 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
/// 0 - R, 1 - L, 2 - D, 3 - U
const int N = 501;
const int oo = 1e9;

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

int n, w, h;
bool stop[N][N];
int dp[10][10][N][N];
char a[N][N];
ii pos[10];
ii lst[N][N][4];

bool ok(int x, int y) {
    if (x < 1 || y < 1 || x > h || y > w) return 0;
    if (a[x][y] == 'x') return 0;
    return 1;
}

bool dig(int x, int y) {
    return (a[x][y] >= '1' && a[x][y] <= '9');
}

/// 0 - R, 1 - L, 2 - D, 3 - U

int A(int dir) { /// ccw
    if (dir == 0) return 3;
    else if (dir == 1) return 2;
    else if (dir == 2) return 0;
    else if (dir == 3) return 1;
}

int C(int dir) { /// cw
    if (dir == 0) return 2;
    else if (dir == 1) return 3;
    else if (dir == 2) return 1;
    else if (dir == 3) return 0;
}

void dfs(int i, int j, int dir) {
//    bug(i);
//    bug(j);
//    bug(dir);
//    cerr<<'\n';
    if (lst[i][j][dir].x != -1) return;
    int ol = dir;
    if (a[i][j] == 'C') dir = C(dir);
    else if (a[i][j] == 'A') dir = A(dir);
    int ni = i + dx[dir];
    int nj = j + dy[dir];
    if (!ok(ni, nj)) {
        stop[i][j] = 1;
        lst[i][j][ol] = {i, j};
//        for (int k = 0; k < 4; k++) if (k != dir) {
//            ni = i + dx[k];
//            nj = j + dy[k];
//            if (ok(ni, nj)) {
//                dfs(ni, nj, k);
//                lst[i][j][k] = lst[ni][nj][k];
//            } else {
//                lst[i][j][k] = {i, j};
//            }
//        }
    }
    else {
        dfs(ni, nj, dir);
        lst[i][j][ol] = lst[ni][nj][dir];
    }
}

int main() {
//    freopen("mrobot.inp", "r", stdin);
//    freopen("mrobot.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> w >> h;
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
            if (dig(i, j)) {
                pos[a[i][j] - '0'].x = i;
                pos[a[i][j] - '0'].y = j;
            }
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            for (int dir = 0; dir < 4; dir++) {
                lst[i][j][dir] = {-1, -1};
            }
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) for (int k = 0; k < 4; k++) {
            dfs(i, j, k);
        }
    }
//    dfs(1, 1, 0);
//    bug(lst[1][1][0].x);
//    bug(lst[1][1][0].y);
//    bug(lst[1][2][0].x);
//    bug(lst[1][2][0].y);
    deque<ii> q;
    for (int i = 1; i <= n; i++) {
        int x = pos[i].x;
        int y = pos[i].y;
        while (q.size()) q.pop_front();
        q.push_back({x, y});
        dp[i][i][x][y] = 0;
        while (q.size()) {
            ii cur = q.front();
            q.pop_front();
            x = cur.x;
            y = cur.y;

            for (int j = 0; j < 4; j++) {
                int nx = lst[x][y][j].x;
                int ny = lst[x][y][j].y;
                if (ok(nx, ny) && dp[i][i][nx][ny] > dp[i][i][x][y] + 1) {
                    dp[i][i][nx][ny] = dp[i][i][x][y] + 1;
                    q.push_back({nx, ny});
                }
            }
        }
    }
    queue<ii> qq;
    for (int l = n - 1; l >= 1; l--) {
        for (int r = l + 1; r <= n; r++) {
            vector<iii> v;
            for (int i = 1; i <= h; i++) {
                for (int j = 1; j <= w; j++) {
                    for (int k = l; k < r; k++) {
                        dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][k][i][j] + dp[k + 1][r][i][j]);
                    }
                }
            }

            for (int i = 1; i <= h; i++) {
                for (int j = 1; j <= w; j++) {
                    if (dp[l][r][i][j] < 1e9)
                        v.push_back(iii(dp[l][r][i][j], {i, j}));
                }
            }

            while (q.size()) q.pop_back();
            while (qq.size()) qq.pop();

            sort(v.begin(), v.end());
            for (int i = 0; i < v.size(); i++) {
                q.push_back({v[i].y.x, v[i].y.y});
            }

            while (q.size()) {
                ii cur = q.front();
                q.pop_front();
                int x = cur.x;
                int y = cur.y;
                #define q2 qq
                q2.push({x, y});
                int tm = dp[l][r][x][y];
                while (q.size()) {
                    int nx = q.front().x;
                    int ny = q.front().y;
                    if (dp[l][r][nx][ny] != tm) break;
                    q.pop_front();
                    q2.push({nx, ny});
                }
                while (q2.size()) {
                    cur = q2.front();
                    q2.pop();
                    x = cur.x;
                    y = cur.y;
                    if (!stop[x][y]) continue;
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = lst[x][y][dir].x;
                        int ny = lst[x][y][dir].y;
                        if (!ok(nx, ny)) continue;
                        if (dp[l][r][nx][ny] > dp[l][r][x][y] + 1) {
                            dp[l][r][nx][ny] = dp[l][r][x][y] + 1;
                            q.push_front({nx, ny});
                        }
                    }
                }
            }
        }
    }
    int ans = 1e9;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) if (stop[i][j]) {
            ans = min(ans, dp[1][n][i][j]);
        }
    }
    if (ans == 1e9) ans = -1;
    cout << ans;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:160:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |             for (int i = 0; i < v.size(); i++) {
      |                             ~~^~~~~~~~~~
robots.cpp: In function 'int A(int)':
robots.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^
robots.cpp: In function 'int C(int)':
robots.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98500 KB Output is correct
2 Correct 41 ms 98496 KB Output is correct
3 Correct 43 ms 98472 KB Output is correct
4 Correct 43 ms 98536 KB Output is correct
5 Correct 43 ms 98488 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98500 KB Output is correct
2 Correct 41 ms 98496 KB Output is correct
3 Correct 43 ms 98472 KB Output is correct
4 Correct 43 ms 98536 KB Output is correct
5 Correct 43 ms 98488 KB Output is correct
6 Correct 42 ms 98496 KB Output is correct
7 Correct 43 ms 98520 KB Output is correct
8 Correct 45 ms 98472 KB Output is correct
9 Correct 39 ms 98452 KB Output is correct
10 Correct 40 ms 98496 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98500 KB Output is correct
2 Correct 41 ms 98496 KB Output is correct
3 Correct 43 ms 98472 KB Output is correct
4 Correct 43 ms 98536 KB Output is correct
5 Correct 43 ms 98488 KB Output is correct
6 Correct 42 ms 98496 KB Output is correct
7 Correct 43 ms 98520 KB Output is correct
8 Correct 45 ms 98472 KB Output is correct
9 Correct 39 ms 98452 KB Output is correct
10 Correct 40 ms 98496 KB Output is correct
11 Correct 127 ms 103624 KB Output is correct
12 Correct 49 ms 102724 KB Output is correct
13 Correct 60 ms 102844 KB Output is correct
14 Correct 319 ms 104488 KB Output is correct
15 Correct 90 ms 103216 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98500 KB Output is correct
2 Correct 41 ms 98496 KB Output is correct
3 Correct 43 ms 98472 KB Output is correct
4 Correct 43 ms 98536 KB Output is correct
5 Correct 43 ms 98488 KB Output is correct
6 Correct 42 ms 98496 KB Output is correct
7 Correct 43 ms 98520 KB Output is correct
8 Correct 45 ms 98472 KB Output is correct
9 Correct 39 ms 98452 KB Output is correct
10 Correct 40 ms 98496 KB Output is correct
11 Correct 127 ms 103624 KB Output is correct
12 Correct 49 ms 102724 KB Output is correct
13 Correct 60 ms 102844 KB Output is correct
14 Correct 319 ms 104488 KB Output is correct
15 Correct 90 ms 103216 KB Output is correct
16 Correct 113 ms 106948 KB Output is correct
17 Correct 877 ms 111416 KB Output is correct
18 Correct 159 ms 108708 KB Output is correct
19 Correct 111 ms 106824 KB Output is correct
20 Correct 484 ms 110060 KB Output is correct