oj.uz

Submission #535733

# Submission time Handle Problem Language Result Execution time Memory
535733 2022-03-11T05:00:20 Z tost_one_love Robots (APIO13_robots) C++17
100 / 100
 891 ms 111636 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 43 ms 98568 KB Output is correct
2 Correct 41 ms 98500 KB Output is correct
3 Correct 47 ms 98508 KB Output is correct
4 Correct 49 ms 98560 KB Output is correct
5 Correct 53 ms 98600 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98568 KB Output is correct
2 Correct 41 ms 98500 KB Output is correct
3 Correct 47 ms 98508 KB Output is correct
4 Correct 49 ms 98560 KB Output is correct
5 Correct 53 ms 98600 KB Output is correct
6 Correct 50 ms 98488 KB Output is correct
7 Correct 40 ms 98504 KB Output is correct
8 Correct 41 ms 98512 KB Output is correct
9 Correct 40 ms 98568 KB Output is correct
10 Correct 48 ms 98584 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98568 KB Output is correct
2 Correct 41 ms 98500 KB Output is correct
3 Correct 47 ms 98508 KB Output is correct
4 Correct 49 ms 98560 KB Output is correct
5 Correct 53 ms 98600 KB Output is correct
6 Correct 50 ms 98488 KB Output is correct
7 Correct 40 ms 98504 KB Output is correct
8 Correct 41 ms 98512 KB Output is correct
9 Correct 40 ms 98568 KB Output is correct
10 Correct 48 ms 98584 KB Output is correct
11 Correct 139 ms 103660 KB Output is correct
12 Correct 51 ms 102880 KB Output is correct
13 Correct 55 ms 102960 KB Output is correct
14 Correct 335 ms 104440 KB Output is correct
15 Correct 90 ms 103308 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98568 KB Output is correct
2 Correct 41 ms 98500 KB Output is correct
3 Correct 47 ms 98508 KB Output is correct
4 Correct 49 ms 98560 KB Output is correct
5 Correct 53 ms 98600 KB Output is correct
6 Correct 50 ms 98488 KB Output is correct
7 Correct 40 ms 98504 KB Output is correct
8 Correct 41 ms 98512 KB Output is correct
9 Correct 40 ms 98568 KB Output is correct
10 Correct 48 ms 98584 KB Output is correct
11 Correct 139 ms 103660 KB Output is correct
12 Correct 51 ms 102880 KB Output is correct
13 Correct 55 ms 102960 KB Output is correct
14 Correct 335 ms 104440 KB Output is correct
15 Correct 90 ms 103308 KB Output is correct
16 Correct 99 ms 107168 KB Output is correct
17 Correct 891 ms 111636 KB Output is correct
18 Correct 163 ms 108960 KB Output is correct
19 Correct 95 ms 107144 KB Output is correct
20 Correct 521 ms 110236 KB Output is correct