Submission #42555

#	Time	Username	Problem	Language	Result	Execution time	Memory
42555		funcsr	Robots (APIO13_robots)	C++14	100 / 100	1234 ms	147816 KiB

robots

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <queue>
#include <cstdio>
using namespace std;
typedef pair<int, int> P;
typedef pair<P, int> P2;
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define INF 1000001919
#define _1 first
#define _2 second
inline void chmin(int &x, int v) { if (x > v) x = v; }
const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, -1, 0, 1};

int N, W, H;
char A[500][500];
P dst[500][500][4];
vector<int> G[500][500][4];
inline int encode(int x, int y, int d) { return (x*H+y)*4+d; }
inline P2 decode(int e) { return P2(P((e/4)/H, (e/4)%H), e%4); }

//const int MAX_D = 10*500*500;
int X[9], Y[9];
int dp[9][9][500][500];
vector<P> Q[500*500];
bool used[500][500];
void bfs(int D[500][500]) {
  rep(i, W) rep(j, H) used[i][j] = false;
  int MAX_D = 0;
  rep(x, W) rep(y, H) if (D[x][y] != INF) MAX_D = max(MAX_D, D[x][y]);
  assert(MAX_D <= 500*500);
  rep(x, W) rep(y, H) if (A[x][y] != 'x' && D[x][y] != INF) Q[D[x][y]].pb(P(x, y));

  vector<P> q;
  int r = 0;
  while (true) {
    if (r > MAX_D && q.empty()) break;
    vector<P> nq;
    if (r <= MAX_D) {
      for (P p : Q[r]) {
        int x = p._1, y = p._2;
        if (!used[x][y]) {
          used[x][y] = true;
          q.pb(P(x, y));
        }
      }
    }
    for (P p : q) {
      int x = p._1, y = p._2;
      rep(k, 4) {
        P np = dst[x][y][k];
        if (np._1 != -1 && !used[np._1][np._2]) {
          used[np._1][np._2] = true;
          D[np._1][np._2] = r+1;
          nq.pb(np);
        }
      }
    }
    q.clear();
    swap(q, nq);
    r++;
  }
  rep(i, MAX_D+1) Q[i].clear();
}

int main() {
  cin >> N >> W >> H;
  rep(y, H) {
    rep(x, W) {
      cin >> A[x][y];
      if ('1' <= A[x][y] && A[x][y] <= '9') X[A[x][y]-'1'] = x, Y[A[x][y]-'1'] = y;
    }
  }
  rep(x, W) rep(y, H) rep(d, 4) dst[x][y][d] = P(-1, -1);
  queue<int> q;
  rep(x, W) rep(y, H) if (A[x][y] != 'x') rep(d, 4) {
    int nx = x+DX[d], ny = y+DY[d], nd = d;
    if (nx<0||nx>=W||ny<0||ny>=H||A[nx][ny]=='x') {
      dst[x][y][d] = P(x, y);
      q.push(encode(x, y, d));
    }
    else {
      if (A[nx][ny] == 'A') nd = (d+3)%4;
      if (A[nx][ny] == 'C') nd = (d+1)%4;
      G[nx][ny][nd].pb(encode(x, y, d));
    }
  }
  while (!q.empty()) {
    P2 e = decode(q.front()); q.pop();
    int x = e._1._1, y = e._1._2, d = e._2;
    for (int te : G[x][y][d]) {
      P2 t = decode(te);
      dst[t._1._1][t._1._2][t._2] = dst[x][y][d];
      q.push(te);
    }
  }
  while (!q.empty()) q.pop();
  rep(x, W) rep(y, H) rep(d, 4) G[x][y][d].clear();

  rep(i, N) rep(j, N) rep(x, W) rep(y, H) dp[i][j][x][y] = INF;
  rep(i, N) dp[i][i][X[i]][Y[i]] = 0;
  for (int len=1; len<=N; len++) {
    rep(l, N) {
      int r = l+len-1;
      if (r >= N) break;
      rep(x, W) rep(y, H) for (int k=l; k<r; k++) chmin(dp[l][r][x][y], dp[l][k][x][y]+dp[k+1][r][x][y]);
      bfs(dp[l][r]);
    }
  }
  int m = INF;
  rep(x, W) rep(y, H) chmin(m, dp[0][N-1][x][y]);
  if (m == INF) m = -1;
  cout << m << "\n";
  return 0;
}

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