oj.uz

Submission #492482

# Submission time Handle Problem Language Result Execution time Memory
492482 2021-12-07T13:54:31 Z Rainbowbunny Portals (BOI14_portals) C++17
100 / 100
 221 ms 181688 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;
const int INF = 1e9;

int r, c;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int sx, sy, ex, ey;
pair <int, int> d[4][MAXN][MAXN];
int dist[MAXN][MAXN], H[MAXN][MAXN];
char a[MAXN][MAXN];
vector <pair <int, int> > Dist[MAXN * MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> r >> c;
    for(int i = 1; i <= r; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == 'S')
            {
                sx = i, sy = j;
            }
            else if(a[i][j] == 'C')
            {
                ex = i, ey = j;
            }
        }
    }
    for(int i = 1; i <= r; i++)
    {
        d[0][i][0] = make_pair(i, 1);
        for(int j = 1; j <= c; j++)
        {
            if(a[i][j] == '#')
            {
                d[0][i][j] = make_pair(i, j + 1);
            }
            else
            {
                d[0][i][j] = d[0][i][j - 1];
            }
        }
        d[1][i][c + 1] = make_pair(i, c);
        for(int j = c; j >= 1; j--)
        {
            if(a[i][j] == '#')
            {
                d[1][i][j] = make_pair(i, j - 1);
            }
            else
            {
                d[1][i][j] = d[1][i][j + 1];
            }
        }
    }
    for(int j = 1; j <= c; j++)
    {
        d[2][0][j] = make_pair(1, j);
        for(int i = 1; i <= r; i++)
        {
            if(a[i][j] == '#')
            {
                d[2][i][j] = make_pair(i + 1, j);
            }
            else
            {
                d[2][i][j] = d[2][i - 1][j];
            }
        }
        d[3][r + 1][j] = make_pair(r, j);
        for(int i = r; i >= 1; i--)
        {
            if(a[i][j] == '#')
            {
                d[3][i][j] = make_pair(i - 1, j);
            }
            else
            {
                d[3][i][j] = d[3][i + 1][j];
            }
        }
    }
    for(int i = 1; i <= r; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            dist[i][j] = INF;
            H[i][j] = INF;
        }
    }
    dist[sx][sy] = 0;
    queue <pair <int, int> > BFS;
    for(int i = 0; i <= r + 1; i++)
    {
        for(int j = 0; j <= c + 1; j++)
        {
            if(a[i][j] == '#' or i == 0 or i == r + 1 or j == 0 or j == c + 1)
            {
                BFS.emplace(i, j);
                H[i][j] = 0;
            }
        }
    }
    while(BFS.empty() == false)
    {
        int nx = BFS.front().first, ny = BFS.front().second;
        BFS.pop();
        for(int i = 0; i < 4; i++)
        {
            int tx = nx + dx[i], ty = ny + dy[i];
            if(H[tx][ty] > H[nx][ny] + 1)
            {
                H[tx][ty] = H[nx][ny] + 1;
                BFS.emplace(tx, ty);
            }
        }
    }
    Dist[0].emplace_back(sx, sy);
    for(int i = 0; i < MAXN * MAXN; i++)
    {
        while(!Dist[i].empty())
        {
            int nx = Dist[i].back().first, ny = Dist[i].back().second;
            Dist[i].pop_back();
            if(dist[nx][ny] != i)
            {
                continue;
            }
            for(int j = 0; j < 4; j++)
            {
                int tx = nx + dx[j], ty = ny + dy[j];
                if(dist[tx][ty] > dist[nx][ny] + 1 and tx > 0 and ty > 0 and tx <= r and ty <= c and a[tx][ty] != '#')
                {
                    dist[tx][ty] = dist[nx][ny] + 1;
                    Dist[i + 1].emplace_back(tx, ty);
                }
                tx = d[j][nx][ny].first, ty = d[j][nx][ny].second;
                if(dist[tx][ty] > dist[nx][ny] + H[nx][ny])
                {
                    dist[tx][ty] = dist[nx][ny] + H[nx][ny];
                    Dist[dist[nx][ny] + H[nx][ny]].emplace_back(tx, ty);
                }
            }
        }
    }
    cout << dist[ex][ey] << '\n';
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94664 KB Output is correct
2 Correct 56 ms 94920 KB Output is correct
3 Correct 56 ms 94964 KB Output is correct
4 Correct 55 ms 94776 KB Output is correct
5 Correct 57 ms 95008 KB Output is correct
6 Correct 58 ms 94968 KB Output is correct
7 Correct 56 ms 95012 KB Output is correct
8 Correct 57 ms 94972 KB Output is correct
9 Correct 55 ms 94800 KB Output is correct
10 Correct 55 ms 94892 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94668 KB Output is correct
2 Correct 59 ms 95012 KB Output is correct
3 Correct 58 ms 95008 KB Output is correct
4 Correct 59 ms 94848 KB Output is correct
5 Correct 57 ms 94964 KB Output is correct
6 Correct 59 ms 94996 KB Output is correct
7 Correct 64 ms 94940 KB Output is correct
8 Correct 64 ms 95016 KB Output is correct
9 Correct 61 ms 96188 KB Output is correct
10 Correct 63 ms 96264 KB Output is correct
11 Correct 60 ms 96200 KB Output is correct
12 Correct 69 ms 96116 KB Output is correct
13 Correct 60 ms 96164 KB Output is correct
14 Correct 56 ms 94840 KB Output is correct
15 Correct 63 ms 96172 KB Output is correct
16 Correct 61 ms 94856 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94696 KB Output is correct
2 Correct 58 ms 94976 KB Output is correct
3 Correct 58 ms 94984 KB Output is correct
4 Correct 57 ms 95016 KB Output is correct
5 Correct 80 ms 101832 KB Output is correct
6 Correct 70 ms 101884 KB Output is correct
7 Correct 65 ms 101856 KB Output is correct
8 Correct 62 ms 102348 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 94776 KB Output is correct
2 Correct 57 ms 94940 KB Output is correct
3 Correct 61 ms 94916 KB Output is correct
4 Correct 58 ms 94852 KB Output is correct
5 Correct 62 ms 94928 KB Output is correct
6 Correct 60 ms 95088 KB Output is correct
7 Correct 58 ms 94920 KB Output is correct
8 Correct 60 ms 95016 KB Output is correct
9 Correct 60 ms 96128 KB Output is correct
10 Correct 58 ms 96144 KB Output is correct
11 Correct 62 ms 96168 KB Output is correct
12 Correct 59 ms 96172 KB Output is correct
13 Correct 58 ms 96060 KB Output is correct
14 Correct 64 ms 101872 KB Output is correct
15 Correct 66 ms 101832 KB Output is correct
16 Correct 64 ms 101876 KB Output is correct
17 Correct 64 ms 101868 KB Output is correct
18 Correct 66 ms 101832 KB Output is correct
19 Correct 68 ms 101996 KB Output is correct
20 Correct 64 ms 102012 KB Output is correct
21 Correct 70 ms 101800 KB Output is correct
22 Correct 68 ms 101812 KB Output is correct
23 Correct 64 ms 101872 KB Output is correct
24 Correct 63 ms 102024 KB Output is correct
25 Correct 60 ms 94816 KB Output is correct
26 Correct 62 ms 96080 KB Output is correct
27 Correct 58 ms 94792 KB Output is correct
28 Correct 73 ms 102376 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 94676 KB Output is correct
2 Correct 59 ms 95012 KB Output is correct
3 Correct 61 ms 95012 KB Output is correct
4 Correct 66 ms 94972 KB Output is correct
5 Correct 59 ms 94916 KB Output is correct
6 Correct 59 ms 94988 KB Output is correct
7 Correct 58 ms 94980 KB Output is correct
8 Correct 57 ms 94920 KB Output is correct
9 Correct 56 ms 96132 KB Output is correct
10 Correct 57 ms 96180 KB Output is correct
11 Correct 59 ms 96172 KB Output is correct
12 Correct 60 ms 96140 KB Output is correct
13 Correct 57 ms 96164 KB Output is correct
14 Correct 63 ms 101832 KB Output is correct
15 Correct 64 ms 101776 KB Output is correct
16 Correct 68 ms 101868 KB Output is correct
17 Correct 67 ms 101776 KB Output is correct
18 Correct 73 ms 101816 KB Output is correct
19 Correct 64 ms 101996 KB Output is correct
20 Correct 64 ms 101948 KB Output is correct
21 Correct 65 ms 101804 KB Output is correct
22 Correct 65 ms 101736 KB Output is correct
23 Correct 64 ms 101764 KB Output is correct
24 Correct 182 ms 168224 KB Output is correct
25 Correct 221 ms 169156 KB Output is correct
26 Correct 200 ms 170568 KB Output is correct
27 Correct 200 ms 170372 KB Output is correct
28 Correct 212 ms 168236 KB Output is correct
29 Correct 196 ms 167680 KB Output is correct
30 Correct 209 ms 167808 KB Output is correct
31 Correct 64 ms 101956 KB Output is correct
32 Correct 203 ms 170884 KB Output is correct
33 Correct 58 ms 94880 KB Output is correct
34 Correct 58 ms 96080 KB Output is correct
35 Correct 198 ms 168096 KB Output is correct
36 Correct 60 ms 94792 KB Output is correct
37 Correct 66 ms 102344 KB Output is correct
38 Correct 201 ms 181688 KB Output is correct
39 Correct 194 ms 165492 KB Output is correct