oj.uz

Submission #287272

# Submission time Handle Problem Language Result Execution time Memory
287272 2020-08-31T14:42:34 Z AlexLuchianov Portals (BOI14_portals) C++14
100 / 100
 479 ms 52616 KB 
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <queue>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 2000;
int const inf = nmax * nmax;
std::string mat[1 + nmax];
int n, m;
bool valid(int x, int y) {
  return 0 <= x && x < n && 0 <= y && y < m;
}

int const iplus[4] = {0, 0, 1, -1};
int const jplus[4] = {1, -1, 0, 0};
int dist[1 + nmax][1 + nmax];

int fast[4][1 + nmax][1 + nmax];

void precompute() {
  std::queue<std::pair<int,int>> q;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++) {
      dist[i][j] = inf;
      if(mat[i][j] != '#') {
        for(int h = 0; h < 4; h++) {
          int newx = i + iplus[h];
          int newy = j + jplus[h];
          if(valid(newx, newy) == 0 || mat[newx][newy] == '#') {
            dist[i][j] = 1;
            q.push({i, j});
          }
        }
      }
    }

  while(0 < q.size()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    for(int h = 0; h < 4; h++) {
      int newx = x + iplus[h];
      int newy = y + jplus[h];
      if(valid(newx, newy) == 1 && mat[newx][newy] != '#' && dist[newx][newy] == inf) {
        q.push({newx, newy});
        dist[newx][newy] = dist[x][y] + 1;
      }
    }
  }

  for(int h = 0; h < 4; h++) {
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        if(mat[i][j] != '#') {
          int newx = i + iplus[h];
          int newy = j + jplus[h];
          if(valid(newx, newy) && mat[newx][newy] != '#')
            fast[h][i][j] = fast[h][newx][newy] + 1;
        }
    for(int i = n - 1; 0 <= i; i--)
      for(int j = m - 1; 0 <= j; j--)
        if(mat[i][j] != '#') {
          int newx = i + iplus[h];
          int newy = j + jplus[h];
          if(valid(newx, newy) && mat[newx][newy] != '#')
            fast[h][i][j] = fast[h][newx][newy] + 1;
        }
  }
}

struct State{
  int x;
  int y;
  int cost;
  bool operator < (State const a) const {
    return a.cost < cost;
  }
};
int dp[1 + nmax][1 + nmax];

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

  std::cin >> n >> m;
  for(int i = 0; i < n; i++)
    std::cin >> mat[i];
  int x, y;
  int x2, y2;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      if(mat[i][j] == 'S') {
        x = i;
        y = j;
      } else if(mat[i][j] == 'C') {
        x2 = i;
        y2 = j;
      }
  precompute();
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      dp[i][j] = inf;

  std::priority_queue<State> pq;
  dp[x][y] = 0;
  pq.push({x, y, 0});

  while(0 < pq.size()) {
    int x = pq.top().x;
    int y = pq.top().y;
    int cost = pq.top().cost;
    pq.pop();
    if(cost == dp[x][y]) {
      for(int h = 0; h < 4; h++) {
        int newx = x + iplus[h];
        int newy = y + jplus[h];
        if(valid(newx, newy) && mat[newx][newy] != '#') {
          if(dp[x][y] + 1 < dp[newx][newy]) {
            dp[newx][newy] = dp[x][y] + 1;
            pq.push({newx, newy, dp[newx][newy]});
          }
        }
        newx = x + iplus[h] * fast[h][x][y];
        newy = y + jplus[h] * fast[h][x][y];
        if(valid(newx, newy) && mat[newx][newy] != '#') {
          if(dp[x][y] + dist[x][y] < dp[newx][newy]) {
            dp[newx][newy] = dp[x][y] + dist[x][y];
            pq.push({newx, newy, dp[newx][newy]});
          }
        }
      }
    }
  }
  std::cout << dp[x2][y2];
  return 0;
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:140:25: warning: 'y2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  140 |   std::cout << dp[x2][y2];
      |                         ^
portals.cpp:140:25: warning: 'x2' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:112:10: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |   pq.push({x, y, 0});
      |   ~~~~~~~^~~~~~~~~~~
portals.cpp:112:10: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
11.0 / 11.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 2 ms 1664 KB Output is correct
10 Correct 2 ms 1664 KB Output is correct
11 Correct 2 ms 1664 KB Output is correct
12 Correct 2 ms 1664 KB Output is correct
13 Correct 2 ms 1664 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 1664 KB Output is correct
16 Correct 1 ms 512 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 11 ms 6400 KB Output is correct
6 Correct 12 ms 6412 KB Output is correct
7 Correct 13 ms 6308 KB Output is correct
8 Correct 8 ms 6340 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 2 ms 1664 KB Output is correct
10 Correct 2 ms 1664 KB Output is correct
11 Correct 2 ms 1664 KB Output is correct
12 Correct 2 ms 1664 KB Output is correct
13 Correct 3 ms 1664 KB Output is correct
14 Correct 11 ms 6400 KB Output is correct
15 Correct 14 ms 6412 KB Output is correct
16 Correct 15 ms 6308 KB Output is correct
17 Correct 10 ms 6276 KB Output is correct
18 Correct 13 ms 6376 KB Output is correct
19 Correct 14 ms 6272 KB Output is correct
20 Correct 13 ms 6272 KB Output is correct
21 Correct 11 ms 6392 KB Output is correct
22 Correct 12 ms 6392 KB Output is correct
23 Correct 13 ms 6408 KB Output is correct
24 Correct 12 ms 6272 KB Output is correct
25 Correct 1 ms 512 KB Output is correct
26 Correct 2 ms 1664 KB Output is correct
27 Correct 1 ms 512 KB Output is correct
28 Correct 9 ms 6340 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 2 ms 1664 KB Output is correct
10 Correct 2 ms 1664 KB Output is correct
11 Correct 2 ms 1664 KB Output is correct
12 Correct 2 ms 1664 KB Output is correct
13 Correct 2 ms 1664 KB Output is correct
14 Correct 11 ms 6400 KB Output is correct
15 Correct 13 ms 6412 KB Output is correct
16 Correct 13 ms 6340 KB Output is correct
17 Correct 10 ms 6276 KB Output is correct
18 Correct 13 ms 6376 KB Output is correct
19 Correct 13 ms 6272 KB Output is correct
20 Correct 12 ms 6272 KB Output is correct
21 Correct 12 ms 6392 KB Output is correct
22 Correct 12 ms 6392 KB Output is correct
23 Correct 12 ms 6408 KB Output is correct
24 Correct 228 ms 49576 KB Output is correct
25 Correct 479 ms 49848 KB Output is correct
26 Correct 355 ms 49528 KB Output is correct
27 Correct 356 ms 49788 KB Output is correct
28 Correct 218 ms 51080 KB Output is correct
29 Correct 236 ms 49548 KB Output is correct
30 Correct 282 ms 49700 KB Output is correct
31 Correct 13 ms 6272 KB Output is correct
32 Correct 351 ms 49528 KB Output is correct
33 Correct 1 ms 512 KB Output is correct
34 Correct 2 ms 1664 KB Output is correct
35 Correct 262 ms 43940 KB Output is correct
36 Correct 1 ms 512 KB Output is correct
37 Correct 8 ms 6340 KB Output is correct
38 Correct 156 ms 52616 KB Output is correct
39 Correct 165 ms 34436 KB Output is correct