oj.uz

Submission #236077

# Submission time Handle Problem Language Result Execution time Memory
236077 2020-05-31T07:08:00 Z VEGAnn Portal (COCI17_portal) C++14
120 / 120
 97 ms 5888 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define a3 array<int, 3>
using namespace std;
const int N = 510;
const int oo = 2e9;
set<a3> st;
int n, m, ex, ey, dst[N][N], step[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int net[4][N][N];
char c[N][N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        dst[i][j] = oo;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        cin >> c[i][j];

        if (c[i][j] == 'C'){
            dst[i][j] = 0;
            st.insert({dst[i][j], i, j});
            c[i][j] = '.';
        }

        if (c[i][j] == 'F'){
            ex = i;
            ey = j;
            c[i][j] = '.';
        }
    }

    for (int i = 0; i < n; i++){
        int lst = m;

        for (int j = m - 1; j >= 0; j--)
            if (c[i][j] == '#')
                lst = j;
            else net[0][i][j] = lst - 1;

        lst = -1;

        for (int j = 0; j < m; j++)
            if (c[i][j] == '#')
                lst = j;
            else net[1][i][j] = lst + 1;
    }

    for (int j = 0; j < m; j++){
        int lst = n;

        for (int i = n - 1; i >= 0; i--)
            if (c[i][j] == '#')
                lst = i;
            else net[2][i][j] = lst - 1;

        lst = -1;

        for (int i = 0; i < n; i++)
            if (c[i][j] == '#')
                lst = i;
            else net[3][i][j] = lst + 1;
    }

    while (sz(st) > 0){
        a3 CR = *st.begin(); st.erase(st.begin());

        int x = CR[1], y = CR[2];

        for (int it = 0; it < 4; it++){
            int cx = x + step[it][0], cy = y + step[it][1];

            if (cx < 0 || cy < 0 || cx >= n || cy >= m || c[cx][cy] == '#') continue;

            if (dst[cx][cy] > dst[x][y] + 1){
                st.erase({dst[cx][cy], cx, cy});
                dst[cx][cy] = dst[x][y] + 1;
                st.insert({dst[cx][cy], cx, cy});
            }
        }

        for (int wh = 0; wh < 4; wh++)
        for (int fr = 0; fr < 4; fr++){
            if (wh == fr) continue;

            int len = 0;

            if (fr < 2)
                len = abs(net[fr][x][y] - y) + 1;
            else len = abs(net[fr][x][y] - x) + 1;

            int cx = x, cy = y;

            if (wh < 2)
                cy = net[wh][x][y];
            else cx = net[wh][x][y];

            if (dst[cx][cy] > dst[x][y] + len){
                st.erase({dst[cx][cy], cx, cy});
                dst[cx][cy] = dst[x][y] + len;
                st.insert({dst[cx][cy], cx, cy});
            }
        }
    }

    if (dst[ex][ey] == oo)
        cout << "nemoguce";
    else cout << dst[ex][ey];

    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2432 KB Output is correct
2 Correct 6 ms 1408 KB Output is correct
3 Correct 11 ms 1408 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2048 KB Output is correct
2 Correct 7 ms 2432 KB Output is correct
3 Correct 14 ms 1664 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4480 KB Output is correct
2 Correct 37 ms 3072 KB Output is correct
3 Correct 26 ms 3456 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5120 KB Output is correct
2 Correct 14 ms 5632 KB Output is correct
3 Correct 41 ms 3584 KB Output is correct
4 Correct 36 ms 4608 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 5760 KB Output is correct
2 Correct 16 ms 5760 KB Output is correct
3 Correct 58 ms 5760 KB Output is correct
4 Correct 64 ms 5888 KB Output is correct