oj.uz

Submission #72206

# Submission time Handle Problem Language Result Execution time Memory
72206 2018-08-26T05:58:05 Z (#2175, xdoju, kazel, pps789) Aquatic Labyrinth (FXCUP3_aqua) C++17
100 / 100
 361 ms 46668 KB 
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll inf = 900LL*900*900*900+9;

int dx[4] = {-1,0,0,1}, dy[4] = {0,1,-1,0};

inline int sq(int x) {
  return x*x;
}

char fl[909][909];
long long dist[909][909];
int g[909][909][4][3];
int n;

int main() {
  scanf("%d",&n);
  int sy, sx, ey, ex;
  for(int i=0;i<n;i++) {
    scanf("%s",fl[i]);
    for(int j=0;j<n;j++) {
      if(fl[i][j] == 'M') {
        sy = i;
        sx = j;
        fl[i][j] = '.';
      } else if(fl[i][j] == 'H') {
        ey = i;
        ex = j;
        fl[i][j] = '.';
      }
    }
  }
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      for(int k=0;k<4;k++) {
        g[i][j][k][0] = -1;
        g[i][j][k][1] = -2;
      }
  // UP DOWN
  for(int j=0;j<n;j++) {
    int pl=0, pr=-1,cl=0;
    bool bl = true;
    for(int i=0;i<n;i++) {
      if(bl) {
        if(fl[i][j] == 'W') continue;
        bl = false;
        cl = i;
      } else {
        if(fl[i][j] == '.') continue;
        int cost = sq(cl-pr-1);
        int cr = i-1;
        for(int k=pl;k<=pr;k++) {
          g[k][j][1][0] = cl;
          g[k][j][1][1] = cr;
          g[k][j][1][2] = cost;
        }
        for(int k=cl;k<=cr;k++) {
          g[k][j][2][0] = pl;
          g[k][j][2][1] = pr;
          g[k][j][2][2] = cost;
        }
        pl = cl;
        pr = cr;
        bl = true;
      }
    }
    if(!bl) {
      int cost = sq(cl-pr-1);
      int cr = n-1;
      for(int k=pl;k<=pr;k++) {
        g[k][j][1][0] = cl;
        g[k][j][1][1] = cr;
        g[k][j][1][2] = cost;
      }
      for(int k=cl;k<=cr;k++) {
        g[k][j][2][0] = pl;
        g[k][j][2][1] = pr;
        g[k][j][2][2] = cost;
      }
    }
  }
  // LEFT RIGHT
  for(int i=0;i<n;i++) {
    int pl=0, pr=-1,cl=0;
    bool bl = true;
    for(int j=0;j<n;j++) {
      if(bl) {
        if(fl[i][j] == 'W') continue;
        bl = false;
        cl = j;
      } else {
        if(fl[i][j] == '.') continue;
        int cost = sq(cl-pr-1);
        int cr = j-1;
        for(int k=pl;k<=pr;k++) {
          g[i][k][3][0] = cl;
          g[i][k][3][1] = cr;
          g[i][k][3][2] = cost;
        }
        for(int k=cl;k<=cr;k++) {
          g[i][k][0][0] = pl;
          g[i][k][0][1] = pr;
          g[i][k][0][2] = cost;
        }
        pl = cl;
        pr = cr;
        bl = true;
      }
    }
    if(!bl) {
      int cost = sq(cl-pr-1);
      int cr = n-1;
      for(int k=pl;k<=pr;k++) {
        g[i][k][3][0] = cl;
        g[i][k][3][1] = cr;
        g[i][k][3][2] = cost;
      }
      for(int k=cl;k<=cr;k++) {
        g[i][k][0][0] = pl;
        g[i][k][0][1] = pr;
        g[i][k][0][2] = cost;
      }
    }
  }
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      dist[i][j] = inf;
  dist[sy][sx] = 0;
  priority_queue<tuple<ll, int, int>> pq;
  pq.emplace(0,sy,sx);
  while(!pq.empty()) {
//    auto [w,y,x] = pq.top();
    ll w;
    int y,x;
    tie(w,y,x) = pq.top();
    if(y == ey && x == ex) break;
    pq.pop();
    w = -w;
    if(w != dist[y][x]) continue;
    for(int k=0;k<4;k++) {
      if(k == 0 || k == 3) {
        for(int xx = g[y][x][k][0]; xx<=g[y][x][k][1]; xx++) {
          ll ww = w + g[y][x][k][2];
          if(dist[y][xx] <= ww) continue;
          dist[y][xx] = ww;
          pq.emplace(-ww,y,xx);
        }
      } else {
        for(int yy = g[y][x][k][0]; yy<=g[y][x][k][1]; yy++) {
          ll ww = w + g[y][x][k][2];
          if(dist[yy][x] <= ww) continue;
          dist[yy][x] = ww;
          pq.emplace(-ww,yy,x);
        }
      }
    }
  }
  if(dist[ey][ex] == inf) puts("-1");
  else printf("%lld\n",dist[ey][ex]);
}

Compilation message

aqua.cpp: In function 'int main()':
aqua.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
aqua.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",fl[i]);
     ~~~~~^~~~~~~~~~~~
aqua.cpp:139:5: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(y == ey && x == ex) break;
     ^~
aqua.cpp:139:16: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(y == ey && x == ex) break;
        ~~~~~~~~^~~~~~~~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 728 KB Output is correct
4 Correct 4 ms 1232 KB Output is correct
5 Correct 4 ms 1692 KB Output is correct
6 Correct 5 ms 1820 KB Output is correct
7 Correct 6 ms 1948 KB Output is correct
8 Correct 6 ms 1948 KB Output is correct
9 Correct 4 ms 1948 KB Output is correct
10 Correct 4 ms 1948 KB Output is correct

Subtask #2
64.0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 728 KB Output is correct
4 Correct 4 ms 1232 KB Output is correct
5 Correct 4 ms 1692 KB Output is correct
6 Correct 5 ms 1820 KB Output is correct
7 Correct 6 ms 1948 KB Output is correct
8 Correct 6 ms 1948 KB Output is correct
9 Correct 4 ms 1948 KB Output is correct
10 Correct 4 ms 1948 KB Output is correct
11 Correct 31 ms 9756 KB Output is correct
12 Correct 61 ms 24236 KB Output is correct
13 Correct 234 ms 36588 KB Output is correct
14 Correct 65 ms 40172 KB Output is correct
15 Correct 62 ms 41580 KB Output is correct
16 Correct 201 ms 46668 KB Output is correct
17 Correct 361 ms 46668 KB Output is correct
18 Correct 139 ms 46668 KB Output is correct
19 Correct 199 ms 46668 KB Output is correct
20 Correct 44 ms 46668 KB Output is correct