oj.uz

Submission #241627

# Submission time Handle Problem Language Result Execution time Memory
241627 2020-06-24T21:03:08 Z ffao Robots (APIO13_robots) C++14
100 / 100
 1125 ms 96692 KB 
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int dist[9][9][510][510];

string board[510];

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

pii dest[510][510][4];
int n, w, h;

pair<int, pair<int, int>> alldist[251000];

pii follow(int x, int y, int d) {
    pii &ret = dest[x][y][d];
    if (ret.first != -1) return ret;

    if (board[x][y] == 'A') d = (d+3)%4;
    else if (board[x][y] == 'C') d=(d+1)%4;

    int nx = x+dx[d], ny = y+dy[d];
    if (nx < 0 || nx >= h || ny < 0 || ny >= w) return ret = {x, y};
    if (board[nx][ny] == 'x') return ret = {x,y};
    return ret = follow(nx,ny,d);
}

void expand(int fr, int to) {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            alldist[i*w+j] = {dist[fr][to][i][j], {i,j}};
        }
    }

    sort(alldist, alldist+(w*h));

    queue<pair<int,int>> q;
    int at = 0;

    while (at < w*h) {
        int aat = at;
        while (at < w*h && alldist[at].first == alldist[aat].first) {
            if (dist[fr][to][alldist[at].second.first][alldist[at].second.second] == alldist[at].first) {
                q.push(alldist[at].second);
            }
            at++;
        }
        
        while (!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop();
            int x = cur.first, y = cur.second;

            while (at < w*h && alldist[at].first == dist[fr][to][x][y] + 1) {
                if (dist[fr][to][alldist[at].second.first][alldist[at].second.second] == alldist[at].first) {
                    q.push(alldist[at].second);
                }
                at++;
            }

            for (int d = 0; d < 4; d++) {
                pii nxt = dest[x][y][d];
                if (dist[fr][to][nxt.first][nxt.second] > dist[fr][to][x][y] + 1) {
                    dist[fr][to][nxt.first][nxt.second] = dist[fr][to][x][y] + 1;
                    q.push(nxt);
                }
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> w >> h;
    for (int i = 0; i < h; i++) cin >> board[i];

    memset(dist,0x3f,sizeof(dist));
    memset(dest, -1, sizeof(dest));

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            for (int d = 0; d < 4; d++) {
                follow(i,j,d);
            }
        }
    }

    for (int oi = 0; oi < h; oi++) {
        for (int oj = 0; oj < w; oj++) {
            if ('1' <= board[oi][oj] && board[oi][oj] <= '9') {
                int idx = board[oi][oj] - '1';
                dist[idx][idx][oi][oj] = 0;

                expand(idx,idx);
            }
        }
    }

    for (int len = 2; len <= n; len++) {
        for (int f = 0; f+len <= n; f++) {
            //cout << len << " " << f << endl;
            for (int spl = f; spl+1 < f+len; spl++) {
                for (int x = 0; x < h; x++) {
                    for (int y = 0; y < w; y++) {
                        dist[f][f+len-1][x][y] = min(dist[f][f+len-1][x][y], dist[f][spl][x][y] + dist[spl+1][f+len-1][x][y]);
                    }
                }
            }

            expand(f, f+len-1);
        }
    }

    int ans = 1000000000;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            ans = min(ans, dist[0][n-1][i][j]);
        }
    }

    cout << (ans == 1000000000 ? -1 : ans);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 91000 KB Output is correct
2 Correct 51 ms 91000 KB Output is correct
3 Correct 50 ms 91000 KB Output is correct
4 Correct 54 ms 91000 KB Output is correct
5 Correct 50 ms 91000 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 91000 KB Output is correct
2 Correct 51 ms 91000 KB Output is correct
3 Correct 50 ms 91000 KB Output is correct
4 Correct 54 ms 91000 KB Output is correct
5 Correct 50 ms 91000 KB Output is correct
6 Correct 48 ms 91000 KB Output is correct
7 Correct 48 ms 91000 KB Output is correct
8 Correct 54 ms 91004 KB Output is correct
9 Correct 51 ms 91000 KB Output is correct
10 Correct 51 ms 91000 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 91000 KB Output is correct
2 Correct 51 ms 91000 KB Output is correct
3 Correct 50 ms 91000 KB Output is correct
4 Correct 54 ms 91000 KB Output is correct
5 Correct 50 ms 91000 KB Output is correct
6 Correct 48 ms 91000 KB Output is correct
7 Correct 48 ms 91000 KB Output is correct
8 Correct 54 ms 91004 KB Output is correct
9 Correct 51 ms 91000 KB Output is correct
10 Correct 51 ms 91000 KB Output is correct
11 Correct 370 ms 92920 KB Output is correct
12 Correct 60 ms 92664 KB Output is correct
13 Correct 261 ms 93000 KB Output is correct
14 Correct 423 ms 92748 KB Output is correct
15 Correct 315 ms 93064 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 91000 KB Output is correct
2 Correct 51 ms 91000 KB Output is correct
3 Correct 50 ms 91000 KB Output is correct
4 Correct 54 ms 91000 KB Output is correct
5 Correct 50 ms 91000 KB Output is correct
6 Correct 48 ms 91000 KB Output is correct
7 Correct 48 ms 91000 KB Output is correct
8 Correct 54 ms 91004 KB Output is correct
9 Correct 51 ms 91000 KB Output is correct
10 Correct 51 ms 91000 KB Output is correct
11 Correct 370 ms 92920 KB Output is correct
12 Correct 60 ms 92664 KB Output is correct
13 Correct 261 ms 93000 KB Output is correct
14 Correct 423 ms 92748 KB Output is correct
15 Correct 315 ms 93064 KB Output is correct
16 Correct 782 ms 96692 KB Output is correct
17 Correct 1109 ms 95844 KB Output is correct
18 Correct 718 ms 96560 KB Output is correct
19 Correct 1125 ms 96544 KB Output is correct
20 Correct 954 ms 95940 KB Output is correct