Submission #477938

#	Time	Username	Problem	Language	Result	Execution time	Memory
477938		jungsnow	Robots (APIO13_robots)	C++14	100 / 100	962 ms	111444 KiB

robots

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40