oj.uz

Submission #42548

# Submission time Handle Problem Language Result Execution time Memory
42548 2018-02-28T04:16:30 Z funcsr Robots (APIO13_robots) C++14
60 / 100
 344 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<P2> G[500][500][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(P2(P(x, y), d));
      }
    }
    while (!q.empty()) {
      int x = q.front()._1._1, y = q.front()._1._2, d = q.front()._2;
      q.pop();
      for (P2 t : G[x][y][d]) {
        //assert(dst[t._1._1][t._1._2][t._2] == P(-1, -1));
        dst[t._1._1][t._1._2][t._2] = dst[x][y][d];
        q.push(t);
      }
    }
  }
  /*
  rep(x, W) rep(y, H) if (A[x][y] != 'x') rep(d, 4) {
    cout<<"dst["<<x<<","<<y<<","<<d<<"]="<<dst[x][y][d]._1<<","<<dst[x][y][d]._2<<"\n";
  }
  */

  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 39 ms 47352 KB Output is correct
2 Correct 39 ms 47456 KB Output is correct
3 Correct 41 ms 47604 KB Output is correct
4 Correct 39 ms 47604 KB Output is correct
5 Correct 39 ms 47616 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB Output is correct
2 Correct 39 ms 47456 KB Output is correct
3 Correct 41 ms 47604 KB Output is correct
4 Correct 39 ms 47604 KB Output is correct
5 Correct 39 ms 47616 KB Output is correct
6 Correct 38 ms 47616 KB Output is correct
7 Correct 38 ms 47636 KB Output is correct
8 Correct 37 ms 47636 KB Output is correct
9 Correct 41 ms 47724 KB Output is correct
10 Correct 38 ms 47724 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB Output is correct
2 Correct 39 ms 47456 KB Output is correct
3 Correct 41 ms 47604 KB Output is correct
4 Correct 39 ms 47604 KB Output is correct
5 Correct 39 ms 47616 KB Output is correct
6 Correct 38 ms 47616 KB Output is correct
7 Correct 38 ms 47636 KB Output is correct
8 Correct 37 ms 47636 KB Output is correct
9 Correct 41 ms 47724 KB Output is correct
10 Correct 38 ms 47724 KB Output is correct
11 Correct 209 ms 105188 KB Output is correct
12 Correct 70 ms 105188 KB Output is correct
13 Correct 120 ms 105188 KB Output is correct
14 Correct 344 ms 107628 KB Output is correct
15 Correct 160 ms 107628 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB Output is correct
2 Correct 39 ms 47456 KB Output is correct
3 Correct 41 ms 47604 KB Output is correct
4 Correct 39 ms 47604 KB Output is correct
5 Correct 39 ms 47616 KB Output is correct
6 Correct 38 ms 47616 KB Output is correct
7 Correct 38 ms 47636 KB Output is correct
8 Correct 37 ms 47636 KB Output is correct
9 Correct 41 ms 47724 KB Output is correct
10 Correct 38 ms 47724 KB Output is correct
11 Correct 209 ms 105188 KB Output is correct
12 Correct 70 ms 105188 KB Output is correct
13 Correct 120 ms 105188 KB Output is correct
14 Correct 344 ms 107628 KB Output is correct
15 Correct 160 ms 107628 KB Output is correct
16 Runtime error 234 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -