oj.uz

Submission #42555

# Submission time Handle Problem Language Result Execution time Memory
42555 2018-02-28T04:54:36 Z funcsr Robots (APIO13_robots) C++14
100 / 100
 1234 ms 147816 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29688 KB Output is correct
2 Correct 25 ms 29792 KB Output is correct
3 Correct 24 ms 29864 KB Output is correct
4 Correct 25 ms 29880 KB Output is correct
5 Correct 25 ms 29880 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29688 KB Output is correct
2 Correct 25 ms 29792 KB Output is correct
3 Correct 24 ms 29864 KB Output is correct
4 Correct 25 ms 29880 KB Output is correct
5 Correct 25 ms 29880 KB Output is correct
6 Correct 25 ms 29936 KB Output is correct
7 Correct 25 ms 29936 KB Output is correct
8 Correct 27 ms 29936 KB Output is correct
9 Correct 25 ms 30008 KB Output is correct
10 Correct 26 ms 30008 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29688 KB Output is correct
2 Correct 25 ms 29792 KB Output is correct
3 Correct 24 ms 29864 KB Output is correct
4 Correct 25 ms 29880 KB Output is correct
5 Correct 25 ms 29880 KB Output is correct
6 Correct 25 ms 29936 KB Output is correct
7 Correct 25 ms 29936 KB Output is correct
8 Correct 27 ms 29936 KB Output is correct
9 Correct 25 ms 30008 KB Output is correct
10 Correct 26 ms 30008 KB Output is correct
11 Correct 205 ms 87596 KB Output is correct
12 Correct 54 ms 87596 KB Output is correct
13 Correct 97 ms 87596 KB Output is correct
14 Correct 363 ms 90096 KB Output is correct
15 Correct 175 ms 90096 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29688 KB Output is correct
2 Correct 25 ms 29792 KB Output is correct
3 Correct 24 ms 29864 KB Output is correct
4 Correct 25 ms 29880 KB Output is correct
5 Correct 25 ms 29880 KB Output is correct
6 Correct 25 ms 29936 KB Output is correct
7 Correct 25 ms 29936 KB Output is correct
8 Correct 27 ms 29936 KB Output is correct
9 Correct 25 ms 30008 KB Output is correct
10 Correct 26 ms 30008 KB Output is correct
11 Correct 205 ms 87596 KB Output is correct
12 Correct 54 ms 87596 KB Output is correct
13 Correct 97 ms 87596 KB Output is correct
14 Correct 363 ms 90096 KB Output is correct
15 Correct 175 ms 90096 KB Output is correct
16 Correct 525 ms 147816 KB Output is correct
17 Correct 1234 ms 147816 KB Output is correct
18 Correct 365 ms 147816 KB Output is correct
19 Correct 307 ms 147816 KB Output is correct
20 Correct 766 ms 147816 KB Output is correct