Submission #254394

# Submission time Handle Problem Language Result Execution time Memory
254394 2020-07-29T23:44:44 Z oscarsierra12 Mecho (IOI09_mecho) C++14
31 / 100
237 ms 13048 KB
#include<bits/stdc++.h>
using namespace std ;
 
const int N = 1000 ;

string ma[N] ;
int dist[N][N], dist2[N][N] ;
int X [] = {0,0,-1,1}, Y[] = {1,-1,0,0} ;
int visi[N][N] ;
int main() {
   int n, s ;
   cin >> n >> s ;
   for ( int i = 0 ; i < n ; ++i ) cin >> ma[i] ;
   queue <pair<int,int>> bfs ;
   pair<int,int> bg, en ;
   for ( int i = 0 ; i < n ; ++i ) {
      for ( int j = 0 ;  j < n ; ++j ) {
          if ( ma[i][j] == 'H' ) bfs.push({i,j}), dist2[i][j] = 0, visi[i][j] = 1 ;
          if ( ma[i][j] == 'T' ) visi[i][j] = 1 ;
          if ( ma[i][j] == 'M' ) bg = {i,j} ;
          if ( ma[i][j] == 'D' ) en = {i,j} ;
      }
   }
   while ( bfs.size() ) {
      pair<int,int> cur = bfs.front() ;
      bfs.pop() ;
      for ( int k = 0 ; k < 4 ; ++k ) {
         int nwx = X[k] + cur.first ;
         int nwy = Y[k] + cur.second ;
         if ( nwx < 0 || nwy < 0 || nwx >= n || nwy >= n || visi[nwx][nwy] ) continue ;
         visi[nwx][nwy] = 1 ;
         dist2[nwx][nwy] = 1 + dist2[cur.first][cur.second] ;
         bfs.push({nwx, nwy}) ; 
      }
   }
   int lw = 0, hg = 3*n ; 
   while ( lw <= hg ) {
      int mid = (lw+hg) / 2 ;
      memset ( visi, 0, sizeof visi ) ; 
      memset ( dist, 0, sizeof dist ) ; 
      bfs.push(bg) ;
      visi[bg.first][bg.second] = 1 ;
      while ( bfs.size() ) {
          pair<int,int> cur = bfs.front() ;
          bfs.pop() ;
          for ( int k = 0 ; k < 4 ; ++k ) {
             int nwx = X[k] + cur.first ;
             int nwy = Y[k] + cur.second ;
             if ( nwx < 0 || nwy < 0 || nwx >= n || nwy >= n || visi[nwx][nwy] || ma[nwx][nwy] == 'T' ) continue ;
             if ( (1 + dist[cur.first][cur.second]) / s + mid >= dist2[nwx][nwy] ) continue ;
             visi[nwx][nwy] = 1 ;
             dist[nwx][nwy] = 1 + dist[cur.first][cur.second] ;
             bfs.push({nwx, nwy}) ; 
          }
      }
      if ( visi[en.first][en.second] ) lw = mid+1 ;
      else hg = mid-1 ;
   }
   cout << hg << endl ;
}
# Verdict Execution time Memory Grader output
1 Correct 7 ms 8192 KB Output is correct
2 Incorrect 6 ms 8192 KB Output isn't correct
3 Correct 6 ms 8192 KB Output is correct
4 Incorrect 6 ms 8192 KB Output isn't correct
5 Correct 8 ms 8192 KB Output is correct
6 Incorrect 7 ms 8192 KB Output isn't correct
7 Incorrect 138 ms 12916 KB Output isn't correct
8 Correct 8 ms 8192 KB Output is correct
9 Correct 7 ms 8192 KB Output is correct
10 Correct 7 ms 8192 KB Output is correct
11 Correct 9 ms 8192 KB Output is correct
12 Incorrect 10 ms 8448 KB Output isn't correct
13 Incorrect 10 ms 8448 KB Output isn't correct
14 Correct 10 ms 8448 KB Output is correct
15 Incorrect 10 ms 8320 KB Output isn't correct
16 Incorrect 11 ms 8320 KB Output isn't correct
17 Incorrect 11 ms 8320 KB Output isn't correct
18 Incorrect 11 ms 8320 KB Output isn't correct
19 Incorrect 8 ms 8320 KB Output isn't correct
20 Incorrect 8 ms 8320 KB Output isn't correct
21 Incorrect 10 ms 8320 KB Output isn't correct
22 Incorrect 8 ms 8320 KB Output isn't correct
23 Incorrect 11 ms 8320 KB Output isn't correct
24 Incorrect 9 ms 8320 KB Output isn't correct
25 Incorrect 9 ms 8448 KB Output isn't correct
26 Incorrect 10 ms 8448 KB Output isn't correct
27 Incorrect 11 ms 8448 KB Output isn't correct
28 Incorrect 12 ms 8448 KB Output isn't correct
29 Incorrect 10 ms 8448 KB Output isn't correct
30 Incorrect 11 ms 8448 KB Output isn't correct
31 Incorrect 12 ms 8448 KB Output isn't correct
32 Incorrect 10 ms 8448 KB Output isn't correct
33 Incorrect 30 ms 9856 KB Output isn't correct
34 Incorrect 36 ms 9856 KB Output isn't correct
35 Correct 35 ms 9856 KB Output is correct
36 Incorrect 31 ms 10112 KB Output isn't correct
37 Incorrect 38 ms 10112 KB Output isn't correct
38 Correct 43 ms 10112 KB Output is correct
39 Incorrect 37 ms 10368 KB Output isn't correct
40 Incorrect 47 ms 10368 KB Output isn't correct
41 Correct 54 ms 10488 KB Output is correct
42 Incorrect 43 ms 10876 KB Output isn't correct
43 Incorrect 61 ms 10908 KB Output isn't correct
44 Correct 78 ms 10880 KB Output is correct
45 Incorrect 54 ms 11128 KB Output isn't correct
46 Incorrect 66 ms 11128 KB Output isn't correct
47 Correct 92 ms 11128 KB Output is correct
48 Incorrect 60 ms 11384 KB Output isn't correct
49 Incorrect 74 ms 11512 KB Output isn't correct
50 Correct 117 ms 11512 KB Output is correct
51 Incorrect 66 ms 11768 KB Output isn't correct
52 Incorrect 85 ms 11768 KB Output isn't correct
53 Correct 126 ms 11896 KB Output is correct
54 Incorrect 82 ms 12024 KB Output isn't correct
55 Incorrect 103 ms 12024 KB Output isn't correct
56 Correct 146 ms 12140 KB Output is correct
57 Incorrect 93 ms 12408 KB Output isn't correct
58 Incorrect 114 ms 12536 KB Output isn't correct
59 Correct 179 ms 12408 KB Output is correct
60 Incorrect 103 ms 12664 KB Output isn't correct
61 Incorrect 131 ms 12664 KB Output isn't correct
62 Correct 193 ms 12792 KB Output is correct
63 Correct 151 ms 12792 KB Output is correct
64 Correct 228 ms 12664 KB Output is correct
65 Correct 237 ms 12792 KB Output is correct
66 Correct 166 ms 12664 KB Output is correct
67 Correct 150 ms 12792 KB Output is correct
68 Correct 82 ms 12664 KB Output is correct
69 Correct 76 ms 12696 KB Output is correct
70 Correct 77 ms 12792 KB Output is correct
71 Correct 79 ms 12792 KB Output is correct
72 Incorrect 61 ms 12664 KB Output isn't correct
73 Incorrect 79 ms 12984 KB Output isn't correct
74 Correct 106 ms 13048 KB Output is correct
75 Correct 119 ms 13032 KB Output is correct
76 Correct 108 ms 12920 KB Output is correct
77 Correct 107 ms 13048 KB Output is correct
78 Correct 113 ms 12920 KB Output is correct
79 Correct 92 ms 12920 KB Output is correct
80 Correct 94 ms 12920 KB Output is correct
81 Correct 106 ms 12920 KB Output is correct
82 Correct 89 ms 12920 KB Output is correct
83 Correct 111 ms 12920 KB Output is correct
84 Correct 110 ms 12944 KB Output is correct
85 Correct 112 ms 12960 KB Output is correct
86 Correct 113 ms 12920 KB Output is correct
87 Correct 117 ms 12920 KB Output is correct
88 Correct 117 ms 12872 KB Output is correct
89 Correct 118 ms 12792 KB Output is correct
90 Correct 120 ms 12828 KB Output is correct
91 Correct 126 ms 12792 KB Output is correct
92 Correct 126 ms 12920 KB Output is correct