oj.uz

Submission #494046

# Submission time Handle Problem Language Result Execution time Memory
494046 2021-12-14T02:24:40 Z goodluck2020 Portals (BOI14_portals) C++14
100 / 100
 304 ms 37664 KB 
#include <bits/stdc++.h>
#define task "portals"

using namespace std;
const int N = 1e3 + 5;
int n, m, A[N][N];
struct Data
{
    int x, y;
} S, C, D;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct Data2
{
    int x, y, w;
} P;
struct cmp
{
    bool operator() (Data2 A, Data2 B)
    {
        return A.w > B.w;
    }
};
int Up[N][N], Down[N][N], Left[N][N], Right[N][N];
void init()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            Left[i][j] = Left[i][j-1] + 1;
            if(A[i][j] == 0) Left[i][j] = 0;
        }
        for(int j = m; j >= 1; j--)
        {
            Right[i][j] = Right[i][j + 1] + 1;
            if(A[i][j] == 0) Right[i][j] = 0;
        }
    }
    for(int j = 1; j <= m; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            Up[i][j] = Up[i-1][j] + 1;
            if(A[i][j] == 0) Up[i][j] = 0;
        }
        for(int i = n; i >= 1; i--)
        {
            Down[i][j] = Down[i + 1][j] + 1;
            if(A[i][j] == 0) Down[i][j] = 0;
        }
    }
}
priority_queue < Data2, vector < Data2 > , cmp > pq;
namespace sub5
{
    queue < Data > Q;
    int Visited[N][N], dist[N][N], wall[N][N];
    void Build()
    {
        for(int i = 0; i <= n + 1; i++)
            for(int j = 0; j <= m + 1; j++)
        if(A[i][j] == 0) Q.push({i, j}), Visited[i][j] = 1;
        while(!Q.empty())
        {
            Data D = Q.front(); Q.pop();
            for(int i = 0; i < 4; i++)
            {
                int x = D.x + dx[i];
                int y = D.y + dy[i];
                if(A[x][y] && !Visited[x][y])
                {
                    Q.push({x, y});
                    wall[x][y] = wall[D.x][D.y] + 1;
                    Visited[x][y] = 1;
                }
            }
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++) Visited[i][j] = 0, dist[i][j] = 1e9;

    }
    void Go(int x, int y, int cost)
    {
        if(dist[x][y] <= dist[P.x][P.y] + cost) return;
        dist[x][y] = dist[P.x][P.y] + cost;
        pq.push({x, y, dist[x][y]});
    }
    void solve()
    {
        Build();
        pq.push({S.x, S.y, 0}); dist[S.x][S.y] = 0;
        while(!pq.empty())
        {
            P = pq.top(); pq.pop();
            for(int i = 0; i < 4; i++)
            {
                int x = P.x + dx[i];
                int y = P.y + dy[i];
                if(A[x][y]) Go(x, y, 1);
            }
                int x, y;
                x = P.x - (Up[P.x][P.y] - 1); y = P.y;
                Go(x, y, wall[P.x][P.y]);
                x = P.x + (Down[P.x][P.y] - 1); y = P.y;
                Go(x, y, wall[P.x][P.y]);
                x = P.x; y = P.y - (Left[P.x][P.y] - 1);
                Go(x, y, wall[P.x][P.y]);
                x = P.x; y = P.y + (Right[P.x][P.y] - 1);
                Go(x, y, wall[P.x][P.y]);
        }
        cout << dist[C.x][C.y];
    }
}
int main()
{
    if(fopen(task ".inp","r"))
    {
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }
    ios_base::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 ch;
            cin >> ch;
            if(ch == 'S') S = {i, j};
            if(ch == 'C') C = {i, j};
            if(ch != '#') A[i][j] = 1;
        }
    init();
    sub5::solve();
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
portals.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 0 ms 588 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 0 ms 460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 2 ms 1868 KB Output is correct
13 Correct 1 ms 1868 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 1868 KB Output is correct
16 Correct 1 ms 460 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 588 KB Output is correct
5 Correct 8 ms 6860 KB Output is correct
6 Correct 10 ms 6860 KB Output is correct
7 Correct 9 ms 6896 KB Output is correct
8 Correct 6 ms 6860 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 0 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 1868 KB Output is correct
10 Correct 2 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 2 ms 1868 KB Output is correct
13 Correct 1 ms 1868 KB Output is correct
14 Correct 8 ms 6860 KB Output is correct
15 Correct 9 ms 6860 KB Output is correct
16 Correct 9 ms 6892 KB Output is correct
17 Correct 7 ms 6732 KB Output is correct
18 Correct 10 ms 6732 KB Output is correct
19 Correct 9 ms 6604 KB Output is correct
20 Correct 9 ms 6704 KB Output is correct
21 Correct 8 ms 6844 KB Output is correct
22 Correct 8 ms 6776 KB Output is correct
23 Correct 9 ms 6836 KB Output is correct
24 Correct 9 ms 6696 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 1 ms 1868 KB Output is correct
27 Correct 0 ms 460 KB Output is correct
28 Correct 5 ms 6860 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 608 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 1868 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 1 ms 1868 KB Output is correct
13 Correct 1 ms 1868 KB Output is correct
14 Correct 8 ms 6872 KB Output is correct
15 Correct 9 ms 6880 KB Output is correct
16 Correct 9 ms 6860 KB Output is correct
17 Correct 8 ms 6732 KB Output is correct
18 Correct 10 ms 6820 KB Output is correct
19 Correct 9 ms 6604 KB Output is correct
20 Correct 10 ms 6720 KB Output is correct
21 Correct 8 ms 6860 KB Output is correct
22 Correct 8 ms 6860 KB Output is correct
23 Correct 9 ms 6880 KB Output is correct
24 Correct 186 ms 34740 KB Output is correct
25 Correct 304 ms 33212 KB Output is correct
26 Correct 234 ms 32900 KB Output is correct
27 Correct 238 ms 33100 KB Output is correct
28 Correct 156 ms 36528 KB Output is correct
29 Correct 168 ms 37572 KB Output is correct
30 Correct 202 ms 37664 KB Output is correct
31 Correct 9 ms 6732 KB Output is correct
32 Correct 227 ms 32860 KB Output is correct
33 Correct 1 ms 460 KB Output is correct
34 Correct 1 ms 1868 KB Output is correct
35 Correct 191 ms 34792 KB Output is correct
36 Correct 1 ms 460 KB Output is correct
37 Correct 6 ms 6860 KB Output is correct
38 Correct 98 ms 35736 KB Output is correct
39 Correct 130 ms 36976 KB Output is correct