oj.uz

Submission #354430

# Submission time Handle Problem Language Result Execution time Memory
354430 2021-01-22T00:26:38 Z thecodingwizard Robots (APIO13_robots) C++11
60 / 100
 1500 ms 61524 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

int n, w, h; 
char A[500][500];
int moveOneRobot[9][500][500]; // cost to move robot i to (j, k)

ii nextPos[4][500][500]; // where we'll end up if we go in direction i from (j, k)
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
ii findNextPos(int dir, int r, int c) {
    if (nextPos[dir][r][c].f != -1) return nextPos[dir][r][c];
    nextPos[dir][r][c] = mp(-2, -2); // cycle

    int r2 = r + dx[dir], c2 = c + dy[dir];
    if (r2 < 0 || r2 >= h || c2 < 0 || c2 >= w || A[r2][c2] == 'x') {
        return nextPos[dir][r][c] = mp(r, c);
    }
    int nextDir = dir;
    if (A[r2][c2] == 'A') {
        nextDir = (dir+1)%4;
    } else if (A[r2][c2] == 'C') {
        nextDir = (dir-1+4)%4;
    }

    return nextPos[dir][r][c] = findNextPos(nextDir, r2, c2);
}

void calcDistForOneRobot(int idx) {
    ii start;
    F0R(i, h) F0R(j, w) {
        if (A[i][j] == '1'+idx) start = mp(i, j);
        moveOneRobot[idx][i][j] = inf;
    }

    queue<ii> q;
    q.push(start); moveOneRobot[idx][start.f][start.s] = 0;
    while (!q.empty()) {
        ii u = q.front(); q.pop();
        F0R(dir, 4) {
            ii v = nextPos[dir][u.f][u.s];
            if (v.f != -2 && moveOneRobot[idx][v.f][v.s] == inf) {
                moveOneRobot[idx][v.f][v.s] = moveOneRobot[idx][u.f][u.s]+1;
                q.push(v);
            }
        }
    }
}

int dp[9][9][500][500];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> w >> h;
    F0R(i, h) F0R(j, w) cin >> A[i][j];

    F0R(i, h) F0R(j, w) F0R(k, 4) nextPos[k][i][j] = mp(-1, -1);
    F0R(i, h) F0R(j, w) F0R(k, 4) nextPos[k][i][j] = findNextPos(k, i, j);

    F0R(i, n) {
        calcDistForOneRobot(i);
    }

    // dp[left][right][r][c] = cost to get [left...right] into location (r, c)
    F0R(delta, n) {
        F0R(left, n) {
            int right = left + delta;
            if (right >= n) continue;

            F0R(r, h) {
                F0R(c, w) {
                    if (delta == 0) {
                        dp[left][right][r][c] = moveOneRobot[left][r][c];
                    } else {
                        dp[left][right][r][c] = inf;
                        FOR(mid, left, right) {
                            dp[left][right][r][c] = min(dp[left][right][r][c], dp[left][mid][r][c] + dp[mid+1][right][r][c]);
                        }
                    }
                }
            }

            priority_queue<pair<int, ii>, vector<pair<int, ii>>, greater<pair<int, ii>>> pq;
            F0R(r, h) F0R(c, w) if (dp[left][right][r][c] != inf) pq.push(mp(dp[left][right][r][c], mp(r, c)));
            while (!pq.empty()) {
                pair<int, ii> u = pq.top(); pq.pop();
                if (u.f != dp[left][right][u.s.f][u.s.s]) continue;
                F0R(dir, 4) {
                    ii v = nextPos[dir][u.s.f][u.s.s];
                    if (v.s < 0) continue;
                    if (dp[left][right][v.f][v.s] > u.f + 1) {
                        dp[left][right][v.f][v.s] = u.f+1;
                        pq.push(mp(u.f+1, v));
                    }
                }
            }
        }
    }

    int ans = inf;
    F0R(r, h) {
        F0R(c, w) {
            ans = min(ans, dp[0][n-1][r][c]);
        }
    }
    if (ans == inf) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 620 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 178 ms 37284 KB Output is correct
12 Correct 16 ms 6960 KB Output is correct
13 Correct 37 ms 25964 KB Output is correct
14 Correct 678 ms 38328 KB Output is correct
15 Correct 123 ms 37148 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 178 ms 37284 KB Output is correct
12 Correct 16 ms 6960 KB Output is correct
13 Correct 37 ms 25964 KB Output is correct
14 Correct 678 ms 38328 KB Output is correct
15 Correct 123 ms 37148 KB Output is correct
16 Correct 114 ms 61524 KB Output is correct
17 Execution timed out 1578 ms 57144 KB Time limit exceeded
18 Halted 0 ms 0 KB -