oj.uz

Submission #261602

# Submission time Handle Problem Language Result Execution time Memory
261602 2020-08-11T22:16:07 Z DS007 Robots (APIO13_robots) C++14
60 / 100
 1500 ms 108396 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 9, W = 500;
int dp[N][N][W][W], pt[W][W], nxt[W][W][5];
vector<int> adj[W * W];
bool explored[W][W][5];
string a[W];
int n, w, h;

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

bool check(int i, int j) {
    if (i < 0 || j < 0 || i >= h || j >= w || a[i][j] == 'x')
        return false;
    return true;
}

int dfs(int i, int j, int dir) {
    if (explored[i][j][dir])
        return nxt[i][j][dir];

    explored[i][j][dir] = true;
    nxt[i][j][dir] = pt[i][j];
    if (a[i][j] != 'A' && a[i][j] != 'C' && a[i][j] != 'x') {
        if (check(i + dx[dir], j + dy[dir]))
            return nxt[i][j][dir] = dfs(i + dx[dir], j + dy[dir], dir);
        else
            return nxt[i][j][dir] = pt[i][j];
    }

    if (a[i][j] == 'C') {
        int nd = dir + 1;
        if (nd == 5)
            nd = 1;

        if (check(i + dx[nd], j + dy[nd]))
            return nxt[i][j][dir] = dfs(i + dx[nd], j + dy[nd], nd);
        else
            return nxt[i][j][dir] = pt[i][j];
    }

    if (a[i][j] == 'A') {
        int nd = dir - 1;
        if (nd == 0)
            nd = 4;

        if (check(i + dx[nd], j + dy[nd]))
            return nxt[i][j][dir] = dfs(i + dx[nd], j + dy[nd], nd);
        else
            return nxt[i][j][dir] = pt[i][j];
    }

    return -1;
}

void dijkstra(int i, int j) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(greater<>())> pq;
    bool explored[w * h] = {};

    for (int k = 0; k < h; k++) {
        for (int l = 0; l < w; l++)
            if (a[k][l] != 'x')
                pq.push({dp[i][j][k][l], pt[k][l]});
    }

    while (!pq.empty()) {
        auto temp = pq.top();
        int d = temp.first, v = temp.second;
        pq.pop();

        if (explored[v])
            continue;

        explored[v] = true;
        for (int k : adj[v]) {
            if (dp[i][j][k / w][k % w] > d + 1)
                dp[i][j][k / w][k % w] = d + 1, pq.push({d + 1, k});
        }
    }
}

int solveTestCase() {
    cin >> n >> w >> h;
    for (int i = 0; i < h; i++) cin >> a[i];

    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++)
            pt[i][j] = w * i + j;
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (!explored[i][j][1])
                dfs(i, j, 1);
            if (!explored[i][j][2])
                dfs(i, j, 2);
            if (!explored[i][j][3])
                dfs(i, j, 3);
            if (!explored[i][j][4])
                dfs(i, j, 4);

            adj[pt[i][j]].push_back(nxt[i][j][1]);
            adj[pt[i][j]].push_back(nxt[i][j][2]);
            adj[pt[i][j]].push_back(nxt[i][j][3]);
            adj[pt[i][j]].push_back(nxt[i][j][4]);
        }
    }

    cerr << check(0 + dx[3], 0 + dy[3]) << "\n";
    cerr << nxt[0][0][1] << " " << nxt[0][0][2] << " " << nxt[0][0][3] << " " << nxt[0][0][4] << "\n";

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < h; k++) {
                for (int l = 0; l < w; l++)
                dp[i][j][k][l] = 1e9;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < h; k++) {
            for (int l = 0; l < w; l++) {
                if (a[k][l] - '0' == i + 1)
                    dp[i][i][k][l] = 0;
            }
        }

        dijkstra(i, i);
    }

    for (int k = 0; k < h; k++) {
        for (int l = 0; l < w; l++)
            cerr << dp[0][0][k][l] << " ";
        cerr << "\n";
    }

    for (int dif = 1; dif < n; dif++) {
        for (int i = 0; i < n; i++) {
            int j = i + dif;
            if (j >= n)
                continue;

            for (int x = i; x < j; x++) {
                for (int k = 0; k < h; k++) {
                    for (int l = 0; l < w; l++)
                        dp[i][j][k][l] = min(dp[i][j][k][l], dp[i][x][k][l] + dp[x + 1][j][k][l]);
                }
            }

            dijkstra(i, j);
        }
    }

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

    cout << (ans == 1e9 ? -1 : ans);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

Compilation message

robots.cpp: In function 'int solveTestCase()':
robots.cpp:164:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 ms 6272 KB Output is correct
4 Correct 5 ms 6400 KB Output is correct
5 Correct 5 ms 6400 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 ms 6272 KB Output is correct
4 Correct 5 ms 6400 KB Output is correct
5 Correct 5 ms 6400 KB Output is correct
6 Correct 4 ms 6272 KB Output is correct
7 Correct 4 ms 6272 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct
9 Correct 5 ms 6272 KB Output is correct
10 Correct 5 ms 6400 KB Output is correct
11 Correct 801 ms 62828 KB Output is correct
12 Correct 411 ms 14992 KB Output is correct
13 Correct 619 ms 44592 KB Output is correct
14 Correct 1084 ms 62820 KB Output is correct
15 Correct 758 ms 62952 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 ms 6272 KB Output is correct
4 Correct 5 ms 6400 KB Output is correct
5 Correct 5 ms 6400 KB Output is correct
6 Correct 4 ms 6272 KB Output is correct
7 Correct 4 ms 6272 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct
9 Correct 5 ms 6272 KB Output is correct
10 Correct 5 ms 6400 KB Output is correct
11 Correct 801 ms 62828 KB Output is correct
12 Correct 411 ms 14992 KB Output is correct
13 Correct 619 ms 44592 KB Output is correct
14 Correct 1084 ms 62820 KB Output is correct
15 Correct 758 ms 62952 KB Output is correct
16 Execution timed out 1591 ms 108396 KB Time limit exceeded
17 Halted 0 ms 0 KB -