oj.uz

Submission #233955

# Submission time Handle Problem Language Result Execution time Memory
233955 2020-05-22T13:28:52 Z parsa_mobed Portals (BOI14_portals) C++14
31 / 100
 21 ms 19520 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair <int , int>
#define F first
#define S second
#define num(i, j) i * (m + 1) + j
#define IsAdjToWall(i, j) !(A[i - 1][j] & A[i + 1][j] & A[i][j - 1] & A[i][j + 1])
const int N = 1e3 + 5;
int A[N][N], dis[N][N], sid[N][N], nxt[N][N][4];
int n, m, S, E;
pii dir[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void BFS() {
    memset(sid, 31, sizeof sid);
    queue <int> q;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        if (A[i][j] == 1 && IsAdjToWall(i, j)) sid[i][j] = 0, q.push(num(i, j));
    while (!q.empty()) {
        int x = q.front() / (m + 1), y = q.front() % (m + 1); q.pop();
        for (int i = 0; i < 4; i++)
            if (A[x + dir[i].F][y + dir[i].S] && sid[x][y] + 1 < sid[x + dir[i].F][y + dir[i].S])
                sid[x + dir[i].F][y + dir[i].S] = sid[x][y] + 1, q.push(num(x + dir[i].F, y + dir[i].S));
    }
}
void Dijkstra() {
    memset(dis, 31, sizeof dis);
    priority_queue <pii, vector<pii>, greater<pii>> pq;
    dis[S / (m + 1)][S % (m + 1)] = 0;
    pq.push({0, S});
    while (!pq.empty()) {
        int x = pq.top().S / (m + 1), y = pq.top().S % (m + 1); pq.pop();
        for (int i = 0; i < 4; i++) {
            int _x = x + dir[i].F, _y = y + dir[i].S;
            if (A[_x][_y] && dis[x][y] + 1 < dis[_x][_y])
                dis[_x][_y] = dis[x][y] + 1, pq.push({dis[_x][_y], num(_x, _y)});
            _x = nxt[x][y][i] / (m + 1), _y = nxt[x][y][i] % (m + 1);
            if (A[_x][_y] && dis[x][y] + sid[x][y] + 1 < dis[_x][_y])
                dis[_x][_y] = dis[x][y] + sid[x][y] + 1, pq.push({dis[_x][_y], num(_x, _y)});
        }
    }
}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        char c; cin >> c;
        if (c != '#') A[i][j] = 1;
        if (c == 'S') S = num(i, j);
        if (c == 'C') E = num(i, j);
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (A[i][j]) {
        nxt[i][j][0] = (A[i - 1][j] ? nxt[i - 1][j][0] : num(i, j));
        nxt[i][j][2] = (A[i][j - 1] ? nxt[i][j - 1][2] : num(i, j));
    }
    for (int i = n; i >= 1; i--) for (int j = m; j >= 1; j--) if (A[i][j]) {
        nxt[i][j][1] = (A[i + 1][j] ? nxt[i + 1][j][1] : num(i, j));
        nxt[i][j][3] = (A[i][j + 1] ? nxt[i][j + 1][3] : num(i, j));
    }
    BFS(), Dijkstra();
    cout << dis[E / (m + 1)][E % (m + 1)] << "\n";
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16128 KB Output is correct
2 Correct 13 ms 16256 KB Output is correct
3 Correct 13 ms 16256 KB Output is correct
4 Correct 13 ms 16256 KB Output is correct
5 Correct 13 ms 16256 KB Output is correct
6 Correct 13 ms 16256 KB Output is correct
7 Correct 14 ms 16256 KB Output is correct
8 Correct 13 ms 16256 KB Output is correct
9 Correct 13 ms 16256 KB Output is correct
10 Correct 13 ms 16256 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16128 KB Output is correct
2 Correct 13 ms 16256 KB Output is correct
3 Correct 13 ms 16256 KB Output is correct
4 Correct 13 ms 16256 KB Output is correct
5 Correct 13 ms 16256 KB Output is correct
6 Correct 12 ms 16256 KB Output is correct
7 Correct 13 ms 16256 KB Output is correct
8 Correct 13 ms 16256 KB Output is correct
9 Correct 13 ms 16640 KB Output is correct
10 Incorrect 13 ms 16768 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16128 KB Output is correct
2 Correct 14 ms 16256 KB Output is correct
3 Correct 13 ms 16256 KB Output is correct
4 Correct 13 ms 16256 KB Output is correct
5 Correct 20 ms 19520 KB Output is correct
6 Correct 21 ms 19512 KB Output is correct
7 Correct 21 ms 19496 KB Output is correct
8 Correct 17 ms 19488 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16152 KB Output is correct
2 Correct 13 ms 16256 KB Output is correct
3 Correct 16 ms 16256 KB Output is correct
4 Correct 13 ms 16256 KB Output is correct
5 Correct 13 ms 16384 KB Output is correct
6 Correct 13 ms 16236 KB Output is correct
7 Correct 14 ms 16256 KB Output is correct
8 Correct 13 ms 16256 KB Output is correct
9 Correct 14 ms 16640 KB Output is correct
10 Incorrect 13 ms 16640 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16128 KB Output is correct
2 Correct 13 ms 16256 KB Output is correct
3 Correct 13 ms 16256 KB Output is correct
4 Correct 13 ms 16256 KB Output is correct
5 Correct 13 ms 16256 KB Output is correct
6 Correct 13 ms 16256 KB Output is correct
7 Correct 13 ms 16256 KB Output is correct
8 Correct 13 ms 16256 KB Output is correct
9 Correct 14 ms 16640 KB Output is correct
10 Incorrect 14 ms 16640 KB Output isn't correct
11 Halted 0 ms 0 KB -