oj.uz

Submission #254400

# Submission time Handle Problem Language Result Execution time Memory
254400 2020-07-30T00:07:31 Z oscarsierra12 Mecho (IOI09_mecho) C++14
4 / 100
 257 ms 12412 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' || ma[i][j] == 'D' ) 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 = n*n + 5 ; 
   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 ;
}

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 8192 KB Output isn't correct
2 Incorrect 8 ms 8192 KB Output isn't correct
3 Incorrect 7 ms 8192 KB Output isn't correct
4 Incorrect 8 ms 8192 KB Output isn't correct
5 Incorrect 8 ms 8192 KB Output isn't correct
6 Incorrect 11 ms 8192 KB Output isn't correct
7 Incorrect 153 ms 12152 KB Output isn't correct
8 Correct 10 ms 8192 KB Output is correct
9 Incorrect 9 ms 8192 KB Output isn't correct
10 Incorrect 8 ms 8192 KB Output isn't correct
11 Incorrect 8 ms 8192 KB Output isn't correct
12 Incorrect 14 ms 8448 KB Output isn't correct
13 Incorrect 15 ms 8320 KB Output isn't correct
14 Correct 13 ms 8448 KB Output is correct
15 Incorrect 8 ms 8320 KB Output isn't correct
16 Incorrect 9 ms 8192 KB Output isn't correct
17 Incorrect 9 ms 8320 KB Output isn't correct
18 Incorrect 8 ms 8320 KB Output isn't correct
19 Incorrect 9 ms 8320 KB Output isn't correct
20 Incorrect 10 ms 8320 KB Output isn't correct
21 Incorrect 10 ms 8320 KB Output isn't correct
22 Incorrect 9 ms 8320 KB Output isn't correct
23 Incorrect 11 ms 8320 KB Output isn't correct
24 Incorrect 12 ms 8320 KB Output isn't correct
25 Incorrect 11 ms 8448 KB Output isn't correct
26 Incorrect 10 ms 8468 KB Output isn't correct
27 Incorrect 12 ms 8448 KB Output isn't correct
28 Incorrect 14 ms 8448 KB Output isn't correct
29 Incorrect 11 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 11 ms 8448 KB Output isn't correct
33 Incorrect 32 ms 9728 KB Output isn't correct
34 Incorrect 38 ms 9728 KB Output isn't correct
35 Incorrect 35 ms 9728 KB Output isn't correct
36 Incorrect 39 ms 9984 KB Output isn't correct
37 Incorrect 50 ms 10024 KB Output isn't correct
38 Incorrect 48 ms 10104 KB Output isn't correct
39 Incorrect 46 ms 10112 KB Output isn't correct
40 Incorrect 55 ms 10112 KB Output isn't correct
41 Incorrect 70 ms 10112 KB Output isn't correct
42 Incorrect 53 ms 10616 KB Output isn't correct
43 Incorrect 65 ms 10616 KB Output isn't correct
44 Incorrect 65 ms 10616 KB Output isn't correct
45 Incorrect 69 ms 10872 KB Output isn't correct
46 Incorrect 80 ms 10872 KB Output isn't correct
47 Incorrect 79 ms 10880 KB Output isn't correct
48 Incorrect 74 ms 11128 KB Output isn't correct
49 Incorrect 92 ms 11136 KB Output isn't correct
50 Incorrect 98 ms 11136 KB Output isn't correct
51 Incorrect 96 ms 11512 KB Output isn't correct
52 Incorrect 103 ms 11384 KB Output isn't correct
53 Incorrect 111 ms 11392 KB Output isn't correct
54 Incorrect 98 ms 11640 KB Output isn't correct
55 Incorrect 128 ms 11628 KB Output isn't correct
56 Incorrect 141 ms 11640 KB Output isn't correct
57 Incorrect 114 ms 11768 KB Output isn't correct
58 Incorrect 147 ms 11768 KB Output isn't correct
59 Incorrect 185 ms 11896 KB Output isn't correct
60 Incorrect 135 ms 12024 KB Output isn't correct
61 Incorrect 166 ms 12028 KB Output isn't correct
62 Incorrect 193 ms 12024 KB Output isn't correct
63 Incorrect 145 ms 12024 KB Output isn't correct
64 Incorrect 257 ms 12024 KB Output isn't correct
65 Incorrect 239 ms 12024 KB Output isn't correct
66 Incorrect 200 ms 12152 KB Output isn't correct
67 Correct 154 ms 12156 KB Output is correct
68 Incorrect 96 ms 12280 KB Output isn't correct
69 Incorrect 94 ms 12152 KB Output isn't correct
70 Incorrect 83 ms 12076 KB Output isn't correct
71 Incorrect 81 ms 12024 KB Output isn't correct
72 Incorrect 103 ms 12152 KB Output isn't correct
73 Incorrect 78 ms 12280 KB Output isn't correct
74 Incorrect 172 ms 12316 KB Output isn't correct
75 Incorrect 118 ms 12280 KB Output isn't correct
76 Incorrect 107 ms 12280 KB Output isn't correct
77 Incorrect 126 ms 12280 KB Output isn't correct
78 Correct 110 ms 12280 KB Output is correct
79 Incorrect 156 ms 12280 KB Output isn't correct
80 Incorrect 108 ms 12280 KB Output isn't correct
81 Incorrect 103 ms 12280 KB Output isn't correct
82 Incorrect 113 ms 12280 KB Output isn't correct
83 Incorrect 114 ms 12280 KB Output isn't correct
84 Incorrect 162 ms 12280 KB Output isn't correct
85 Incorrect 122 ms 12280 KB Output isn't correct
86 Incorrect 119 ms 12280 KB Output isn't correct
87 Incorrect 125 ms 12288 KB Output isn't correct
88 Incorrect 136 ms 12412 KB Output isn't correct
89 Incorrect 186 ms 12280 KB Output isn't correct
90 Incorrect 130 ms 12280 KB Output isn't correct
91 Incorrect 145 ms 12152 KB Output isn't correct
92 Incorrect 126 ms 12280 KB Output isn't correct