oj.uz

Submission #207662

# Submission time Handle Problem Language Result Execution time Memory
207662 2020-03-08T10:08:01 Z PeppaPig Robots (APIO13_robots) C++14
100 / 100
 1010 ms 59996 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

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

struct item {
    int r, c, id;
    item(int r, int c, int id) : r(r), c(c), id(id) {}
};

int n, w, h, mp[10][10], dp[45][N][N];
char A[N][N];
pii nex[4][N][N];
vector<item> process[45];

pii find_next(int r, int c, int dir) {
    if(nex[dir][r][c] == pii(-1, -1) && A[r][c] != 'x') {
        int ndir = dir;
        if(A[r][c] == 'C') ndir = (dir + 1) % 4;
        if(A[r][c] == 'A') ndir = (dir + 3) % 4;
        int nr = r + dx[ndir], nc = c + dy[ndir];
        if(nr < 1 || nr > h || nc < 1 || nc > w || A[nr][nc] == 'x')
            nex[dir][r][c] = pii(r, c);
        else nex[dir][r][c] = find_next(nr, nc, ndir);
    }
    return nex[dir][r][c];
}

int main() {
    fill_n(nex[0][0], N * N * 4, pii(-1, -1));
    fill_n(dp[0][0], 45 * N * N, 1e9);

    scanf("%d %d %d", &n, &w, &h);
    for(int i = 1; i <= h; i++) scanf(" %s", A[i] + 1);

    for(int i = 1; i <= h; i++) 
        for(int j = 1; j <= w; j++)
            for(int k = 0; k < 4; k++)
                find_next(i, j, k);
    for(int i = 1, ptr = 0; i <= n; i++) for(int j = i; j <= n; j++)
        mp[i][j] = ptr++;

    queue<item> Q;
    for(int k = 1; k <= n; k++) for(int x = 1, y = k; y <= n; x++, y++) {
        vector<item> proc;
        for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) {
            if(A[i][j] == 'x') continue;
            if(k == 1) {
                if(A[i][j] == '0' + x) {
                    int now = mp[A[i][j] - '0'][A[i][j] - '0'];
                    proc.emplace_back(i, j, now);
                    dp[now][i][j] = 0;
                }
            } else {
                int now = mp[x][y];
                for(int l = x; l < y; l++) {
                    int L = mp[x][l], R = mp[l + 1][y];
                    dp[now][i][j] = min(dp[now][i][j], dp[L][i][j] + dp[R][i][j]);
                }
                proc.emplace_back(i, j, now);
            }
        }

        sort(proc.begin(), proc.end(), [&](item &a, item &b) {
            return dp[a.id][a.r][a.c] < dp[b.id][b.r][b.c];
        });
        for(item &now : proc) {
            Q.emplace(now);
            while(!Q.empty()) {
                item u = Q.front(); Q.pop();
                for(int i = 0; i < 4; i++) {
                    int nr = u.r + dx[i], nc = u.c + dy[i];
                    if(nr < 1 || nr > h || nc < 1 || nc > w || A[nr][nc] == 'x')
                        continue;
                    pii v = nex[i][nr][nc];
                    if(dp[u.id][u.r][u.c] + 1 < dp[u.id][v.x][v.y]) {
                        dp[u.id][v.x][v.y] = dp[u.id][u.r][u.c] + 1;
                        Q.emplace(v.x, v.y, u.id);
                    }
                }
            }
        }
    }
    int ans = 1e9;
    for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++)
        ans = min(ans, dp[mp[1][n]][i][j]); 
    if(ans != 1e9) printf("%d\n", ans);
    else printf("-1\n");

    return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &w, &h);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:41:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= h; i++) scanf(" %s", A[i] + 1);
                                 ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 53240 KB Output is correct
2 Correct 34 ms 53240 KB Output is correct
3 Correct 35 ms 53240 KB Output is correct
4 Correct 36 ms 53244 KB Output is correct
5 Correct 44 ms 53216 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 53240 KB Output is correct
2 Correct 34 ms 53240 KB Output is correct
3 Correct 35 ms 53240 KB Output is correct
4 Correct 36 ms 53244 KB Output is correct
5 Correct 44 ms 53216 KB Output is correct
6 Correct 35 ms 53240 KB Output is correct
7 Correct 35 ms 53156 KB Output is correct
8 Correct 42 ms 53240 KB Output is correct
9 Correct 37 ms 53188 KB Output is correct
10 Correct 35 ms 53240 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 53240 KB Output is correct
2 Correct 34 ms 53240 KB Output is correct
3 Correct 35 ms 53240 KB Output is correct
4 Correct 36 ms 53244 KB Output is correct
5 Correct 44 ms 53216 KB Output is correct
6 Correct 35 ms 53240 KB Output is correct
7 Correct 35 ms 53156 KB Output is correct
8 Correct 42 ms 53240 KB Output is correct
9 Correct 37 ms 53188 KB Output is correct
10 Correct 35 ms 53240 KB Output is correct
11 Correct 258 ms 54700 KB Output is correct
12 Correct 43 ms 53448 KB Output is correct
13 Correct 152 ms 54956 KB Output is correct
14 Correct 329 ms 54828 KB Output is correct
15 Correct 224 ms 54628 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 53240 KB Output is correct
2 Correct 34 ms 53240 KB Output is correct
3 Correct 35 ms 53240 KB Output is correct
4 Correct 36 ms 53244 KB Output is correct
5 Correct 44 ms 53216 KB Output is correct
6 Correct 35 ms 53240 KB Output is correct
7 Correct 35 ms 53156 KB Output is correct
8 Correct 42 ms 53240 KB Output is correct
9 Correct 37 ms 53188 KB Output is correct
10 Correct 35 ms 53240 KB Output is correct
11 Correct 258 ms 54700 KB Output is correct
12 Correct 43 ms 53448 KB Output is correct
13 Correct 152 ms 54956 KB Output is correct
14 Correct 329 ms 54828 KB Output is correct
15 Correct 224 ms 54628 KB Output is correct
16 Correct 1010 ms 59996 KB Output is correct
17 Correct 921 ms 56948 KB Output is correct
18 Correct 552 ms 56740 KB Output is correct
19 Correct 503 ms 56808 KB Output is correct
20 Correct 742 ms 56944 KB Output is correct