oj.uz

Submission #477938

# Submission time Handle Problem Language Result Execution time Memory
477938 2021-10-04T17:08:44 Z jungsnow Robots (APIO13_robots) C++14
100 / 100
 962 ms 111444 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;

const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
const int maxn = 501, INF = 1e9;

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

int N, W, H;
int dp[10][10][maxn][maxn];
char A[maxn][maxn];
bool stop[maxn][maxn];

ii pos[10], lst[maxn][maxn][4];

void minn(int &a, int b) {
  if (a > b) a = b;
}

bool ok(int x, int y) {
  if (x < 1 || y < 1 || x > H || y > W) return 0;
  if (A[x][y] == 'x') return 0;
  return 1;
}

bool dig(int x, int y) {
  return (A[x][y] >= '1' && A[x][y] <= '9');
}

int a[] = {3, 2, 0, 1};
int c[] = {2, 3, 1, 0};

void dfs(int i, int j, int dir) {
  if (lst[i][j][dir].x != -1) return;
  int ol = dir;
  if (A[i][j] == 'C') dir = c[dir];
  if (A[i][j] == 'A') dir = a[dir];
  int ni = i + dx[dir], nj = j + dy[dir];
  if (!ok(ni, nj)) {
    stop[i][j] = 1;
    lst[i][j][ol] = {i, j};
  } else {
    dfs(ni, nj, dir);
    lst[i][j][ol] = lst[ni][nj][dir];
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
//  freopen("mrobot.inp", "r", stdin);
//  freopen("mrobot.out", "w", stdout);
  cin >> N >> W >> H;
  for (int i = 1; i <= H; ++i) {
    for (int j = 1; j <= W; ++j) {
      cin >> A[i][j];
      if (dig(i, j)) {
        pos[A[i][j] - '0'].x = i;
        pos[A[i][j] - '0'].y = j;
      }
    }
  }
  for (int i = 1; i <= H; ++i) {
    for (int j = 1; j <= W; ++j) {
      for (int dir = 0; dir < 4; ++dir) {
        lst[i][j][dir] = {-1, -1};
      }
    }
  }
  for (int i = 1; i <= H; ++i) {
    for (int j = 1; j <= W; ++j) {
      for (int dir = 0; dir < 4; ++dir) {
        dfs(i, j, dir);
      }
    }
  }
  memset(dp, 0x3f, sizeof dp);
  deque<ii> q;
  for (int i = 1; i <= N; ++i) {
    int x = pos[i].x, y = pos[i].y;
    q.push_back({x, y});
    dp[i][i][x][y] = 0;
    while (q.size()) {
      ii cur = q.front(); q.pop_front();
      tie(x, y) = cur;
      for (int j = 0; j < 4; ++j) {
        int nx, ny;
        tie(nx, ny) = lst[x][y][j];
        if (ok(nx, ny) && dp[i][i][nx][ny] > dp[i][i][x][y] + 1) {
          dp[i][i][nx][ny] = dp[i][i][x][y] + 1;
          q.push_back({nx, ny});
        }
      }
    }
  }
  queue<ii> q2;
  for (int l = N - 1; l >= 1; --l) {
    for (int r = l + 1; r <= N; ++r) {
      vector<iii> v;
      for (int i = 1; i <= H; ++i)
        for (int j = 1; j <= W; ++j)
          for (int k = l; k < r; ++k)
            minn(dp[l][r][i][j], dp[l][k][i][j] + dp[k + 1][r][i][j]);
      for (int i = 1; i <= H; ++i)
        for (int j = 1; j <= W; ++j)
          if (dp[l][r][i][j] < INF && stop[i][j])
            v.push_back({dp[l][r][i][j], ii(i, j)});
      sort(v.begin(), v.end());
      for (int i = 0; i < v.size(); ++i)
        q.push_back({v[i].y.x, v[i].y.y});
      while (q.size()) {
        ii cur = q.front(); q.pop_front();
        int x = cur.x, y = cur.y;
        int tm = dp[l][r][x][y];
        q2.push({x, y});
        while (q.size()) {
          int nx, ny;
          tie(nx, ny) = q.front();
          if (dp[l][r][nx][ny] != tm) break;
          q.pop_front();
          q2.push({nx, ny});
        }
        while (q2.size()) {
          cur = q2.front(); q2.pop();
          int x = cur.x, y = cur.y;
          if (!stop[x][y]) continue;
          for (int k = 0; k < 4; ++k) {
            int nx, ny;
            tie(nx, ny) = lst[x][y][k];
            if (!ok(nx, ny)) continue;
            if (dp[l][r][nx][ny] > dp[l][r][x][y] + 1) {
              dp[l][r][nx][ny] = dp[l][r][x][y] + 1;
              q.push_front({nx, ny});
            }
          }
        }
      }
    }
  }
  int ans = INF;
  for (int i = 1; i <= H; ++i)
    for (int j = 1; j <= W; ++j)
      if (stop[i][j]) minn(ans, dp[1][N][i][j]);
  if (ans == INF) ans = -1;
  cout<<ans<<'\n';
  return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:113:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |       for (int i = 0; i < v.size(); ++i)
      |                       ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98436 KB Output is correct
2 Correct 43 ms 98500 KB Output is correct
3 Correct 47 ms 98628 KB Output is correct
4 Correct 39 ms 98532 KB Output is correct
5 Correct 39 ms 98508 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98436 KB Output is correct
2 Correct 43 ms 98500 KB Output is correct
3 Correct 47 ms 98628 KB Output is correct
4 Correct 39 ms 98532 KB Output is correct
5 Correct 39 ms 98508 KB Output is correct
6 Correct 39 ms 98500 KB Output is correct
7 Correct 48 ms 98532 KB Output is correct
8 Correct 50 ms 98500 KB Output is correct
9 Correct 40 ms 98552 KB Output is correct
10 Correct 44 ms 98508 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98436 KB Output is correct
2 Correct 43 ms 98500 KB Output is correct
3 Correct 47 ms 98628 KB Output is correct
4 Correct 39 ms 98532 KB Output is correct
5 Correct 39 ms 98508 KB Output is correct
6 Correct 39 ms 98500 KB Output is correct
7 Correct 48 ms 98532 KB Output is correct
8 Correct 50 ms 98500 KB Output is correct
9 Correct 40 ms 98552 KB Output is correct
10 Correct 44 ms 98508 KB Output is correct
11 Correct 128 ms 103564 KB Output is correct
12 Correct 60 ms 102776 KB Output is correct
13 Correct 71 ms 102872 KB Output is correct
14 Correct 316 ms 104324 KB Output is correct
15 Correct 93 ms 103288 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98436 KB Output is correct
2 Correct 43 ms 98500 KB Output is correct
3 Correct 47 ms 98628 KB Output is correct
4 Correct 39 ms 98532 KB Output is correct
5 Correct 39 ms 98508 KB Output is correct
6 Correct 39 ms 98500 KB Output is correct
7 Correct 48 ms 98532 KB Output is correct
8 Correct 50 ms 98500 KB Output is correct
9 Correct 40 ms 98552 KB Output is correct
10 Correct 44 ms 98508 KB Output is correct
11 Correct 128 ms 103564 KB Output is correct
12 Correct 60 ms 102776 KB Output is correct
13 Correct 71 ms 102872 KB Output is correct
14 Correct 316 ms 104324 KB Output is correct
15 Correct 93 ms 103288 KB Output is correct
16 Correct 113 ms 106876 KB Output is correct
17 Correct 962 ms 111444 KB Output is correct
18 Correct 151 ms 108688 KB Output is correct
19 Correct 103 ms 106924 KB Output is correct
20 Correct 498 ms 109868 KB Output is correct