oj.uz

Submission #723494

# Submission time Handle Problem Language Result Execution time Memory
723494 2023-04-14T00:58:04 Z quiet_space Robots (APIO13_robots) C++14
100 / 100
 848 ms 68452 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 4 ms 6228 KB Output is correct
5 Correct 3 ms 6308 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 4 ms 6228 KB Output is correct
5 Correct 3 ms 6308 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 3 ms 6184 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 5 ms 6308 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 4 ms 6228 KB Output is correct
5 Correct 3 ms 6308 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 3 ms 6184 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 5 ms 6308 KB Output is correct
11 Correct 187 ms 28488 KB Output is correct
12 Correct 19 ms 11476 KB Output is correct
13 Correct 103 ms 23072 KB Output is correct
14 Correct 289 ms 28576 KB Output is correct
15 Correct 169 ms 28480 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 4 ms 6228 KB Output is correct
5 Correct 3 ms 6308 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 3 ms 6184 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 5 ms 6308 KB Output is correct
11 Correct 187 ms 28488 KB Output is correct
12 Correct 19 ms 11476 KB Output is correct
13 Correct 103 ms 23072 KB Output is correct
14 Correct 289 ms 28576 KB Output is correct
15 Correct 169 ms 28480 KB Output is correct
16 Correct 499 ms 68452 KB Output is correct
17 Correct 848 ms 64224 KB Output is correct
18 Correct 512 ms 64060 KB Output is correct
19 Correct 469 ms 64708 KB Output is correct
20 Correct 645 ms 64212 KB Output is correct