oj.uz

Submission #42549

# Submission time Handle Problem Language Result Execution time Memory
42549 2018-02-28T04:19:28 Z funcsr Robots (APIO13_robots) C++14
60 / 100
 345 ms 163840 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];
int start;
/*
inline void tle_check() {
  double passed = (double)(clock()-start) / (double)CLOCKS_PER_SEC;
  if (passed>=1.0) {
    //cout<<passed<<" passed\n";
    abort();
  }
}
*/
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;
//const int MAX_D = 10*1000;
int X[9], Y[9];
int dp[9][9][500][500];
vector<P> Q[4*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));
  //rep(x, W) rep(y, H) if (D[x][y] != INF)cout<<"("<<x<<","<<y<<")->"<<D[x][y]<<"\n";
  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();
}

queue<P2> q;
int main() {
  //start = clock();
  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);
  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(P2(P(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()) {
    int x = q.front()._1._1, y = q.front()._1._2, d = q.front()._2;
    q.pop();
    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(t);
    }
  }
  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 38 ms 47352 KB Output is correct
2 Correct 38 ms 47456 KB Output is correct
3 Correct 38 ms 47456 KB Output is correct
4 Correct 38 ms 47572 KB Output is correct
5 Correct 39 ms 47588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47352 KB Output is correct
2 Correct 38 ms 47456 KB Output is correct
3 Correct 38 ms 47456 KB Output is correct
4 Correct 38 ms 47572 KB Output is correct
5 Correct 39 ms 47588 KB Output is correct
6 Correct 38 ms 47588 KB Output is correct
7 Correct 40 ms 47588 KB Output is correct
8 Correct 39 ms 47588 KB Output is correct
9 Correct 41 ms 47588 KB Output is correct
10 Correct 40 ms 47708 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47352 KB Output is correct
2 Correct 38 ms 47456 KB Output is correct
3 Correct 38 ms 47456 KB Output is correct
4 Correct 38 ms 47572 KB Output is correct
5 Correct 39 ms 47588 KB Output is correct
6 Correct 38 ms 47588 KB Output is correct
7 Correct 40 ms 47588 KB Output is correct
8 Correct 39 ms 47588 KB Output is correct
9 Correct 41 ms 47588 KB Output is correct
10 Correct 40 ms 47708 KB Output is correct
11 Correct 202 ms 105208 KB Output is correct
12 Correct 65 ms 105208 KB Output is correct
13 Correct 102 ms 105208 KB Output is correct
14 Correct 345 ms 107628 KB Output is correct
15 Correct 162 ms 107628 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47352 KB Output is correct
2 Correct 38 ms 47456 KB Output is correct
3 Correct 38 ms 47456 KB Output is correct
4 Correct 38 ms 47572 KB Output is correct
5 Correct 39 ms 47588 KB Output is correct
6 Correct 38 ms 47588 KB Output is correct
7 Correct 40 ms 47588 KB Output is correct
8 Correct 39 ms 47588 KB Output is correct
9 Correct 41 ms 47588 KB Output is correct
10 Correct 40 ms 47708 KB Output is correct
11 Correct 202 ms 105208 KB Output is correct
12 Correct 65 ms 105208 KB Output is correct
13 Correct 102 ms 105208 KB Output is correct
14 Correct 345 ms 107628 KB Output is correct
15 Correct 162 ms 107628 KB Output is correct
16 Runtime error 232 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -