Submission #723494

#	Time	Username	Problem	Language	Result	Execution time	Memory
723494		quiet_space	Robots (APIO13_robots)	C++14	100 / 100	848 ms	68452 KiB

robots

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
using pii = std::pair <int, int>;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int maxN = 10;
const int maxn = 505;
const int maxv = 250005;
char c[maxn][maxn];
int d[maxN][maxN][maxv], id[maxn][maxn], t[maxn][maxn][4];
bool ins[maxn][maxn][4];
std::vector <int> v[maxv];
int dfs (int x, int y, int k) {
  if(ins[x][y][k]) return t[x][y][k] = -1;
  if(t[x][y][k] != -2) return t[x][y][k];
  ins[x][y][k] = 1; int X = x + dx[k], Y = y + dy[k];
  if(c[X][Y] == 'x') t[x][y][k] = id[x][y];
  else if(c[X][Y] == 'A') t[x][y][k] = dfs (X, Y, (k + 3) % 4);
  else if(c[X][Y] == 'C') t[x][y][k] = dfs (X, Y, (k + 1) % 4);
  else t[x][y][k] = dfs (X, Y, k);
  ins[x][y][k] = 0; return t[x][y][k];
}
std::queue <pii> q, Q;
std::vector <pii> vec;
int main (void) {
  int N = read(), m = read(), n = read(), o = n * m;
  FOR(i,1,n) {
    scanf("%s", c[i]+1);
    FOR(j,1,m) id[i][j] = (i - 1) * m + j;
  }
  FOR(i,1,n) c[i][0] = c[i][m+1] = 'x';
  FOR(j,1,m) c[0][j] = c[n+1][j] = 'x';
  FOR(i,1,n) FOR(j,1,m) if(c[i][j] != 'x') FOR(k,0,3) t[i][j][k] = -2;
  FOR(i,1,n) FOR(j,1,m) if(c[i][j] != 'x') FOR(k,0,3) dfs (i, j, k);
  FOR(i,1,n) FOR(j,1,m) if(c[i][j] != 'x') FOR(k,0,3) if(t[i][j][k] != -1) v[id[i][j]].push_back (t[i][j][k]);
  FOR(l,1,N) FOR(r,l,N) std::fill (d[l][r]+1, d[l][r]+o+1, 1 << 29);
  ROF(l,N,1) FOR(r,1,N) {
    if(l == r) { FOR(i,1,n) FOR(j,1,m) if(c[i][j] == l + '0') d[l][r][id[i][j]] = 0; }
    else FOR(M,l,r-1) FOR(i,1,o) d[l][r][i] = std::min(d[l][r][i], d[l][M][i] + d[M+1][r][i]);
    FOR(i,1,o) if(d[l][r][i] != 1 << 29) vec.emplace_back (d[l][r][i], i);
    std::sort(vec.begin(), vec.end());
    for(auto&it:vec) q.push (it);
    vec.clear(); pii cur;
    while(!q.empty() || !Q.empty()) {
      if(Q.empty() || !q.empty() && q.front().first < Q.front().first) 
        cur = q.front(), q.pop(); else cur = Q.front(), Q.pop();
      if(cur.first > d[l][r][cur.second]) continue;
      for(auto&it:v[cur.second]) if(d[l][r][it] > d[l][r][cur.second] + 1)
        Q.emplace (d[l][r][it] = d[l][r][cur.second] + 1, it);
    }
  }
  int ans = *std::min_element (d[1][N]+1, d[1][N]+o+1);
  printf("%d\n", ans == 1 << 29 ? -1 : ans);
  return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:52:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |       if(Q.empty() || !q.empty() && q.front().first < Q.front().first)
      |                       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%s", c[i]+1);
      |     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40