oj.uz

Submission #1072162

# Submission time Handle Problem Language Result Execution time Memory
1072162 2024-08-23T15:06:40 Z 7again Mecho (IOI09_mecho) C++17
9 / 100
 304 ms 12472 KB 
#include <bits/stdc++.h>

using namespace std ;

const int N = 801 ;
int dx[]{0 , 0 , 1 , -1} ;
int dy[]{1 , -1 , 0 , 0} ;


int n , s ;
pair <int , int> Honey , Home ;
char a[N][N] ;

bool inside(int x , int y) {
    return (x >= 0 && y >= 0 && x < n && y < n && a[x][y] != 'T') ;
}
bool val(int x , int y) {
    return  x / s < y ;
}
int ok(int time) {

    int mn2[n][n] ;
    fill_n(&mn2[0][0] , n*n , 1e9) ;
    queue<pair <int , int>>  q2 ;
    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < n ; j++) {
            if(a[i][j] == 'H') {
                q2.push({i, j}) ;
                mn2[i][j] = 0 ;
            }
        }
    }
    while(q2.size()) {
        pair <int , int> t = q2.front() ;
        q2.pop() ;
        for(int i = 0 ; i < 4 ; i++) {
            int x = t.first + dx[i] ;
            int y = t.second + dy[i] ;
            if(inside(x , y) &&  mn2[t.first][t.second] + 1 < mn2[x][y]) {
                mn2[x][y] = mn2[t.first][t.second] + 1 ;
                q2.push({x, y}) ;
            }
        }
    }

    int mn[n][n] ;
    fill_n(&mn[0][0] , n * n , 1e9 ) ;
    queue <pair <int , int>> q ;
    mn[Honey.first][Honey.second] = 0 ;
    if(mn2[Honey.first][Honey.second] > time)
        q.push(Honey) ;
    while(!q.empty()) {
        pair <int , int> t = q.front() ;
        q.pop() ;
        for(int i = 0 ; i < 4 ; i++) {
            int x = t.first + dx[i] ;
            int y = t.second + dy[i] ;
            if(val(mn[t.first][t.second] + 1 , mn2[x][y] - time) && inside(x , y) && mn[t.first][t.second] + 1 < mn[x][y]) {
                mn[x][y] = mn[t.first][t.second] + 1 ;
                q.push({x , y}) ;
            }
        }
    }
    for(int i = 0 ; i < 4 ; i++){
        int x = Honey.first + dx[i] ;
        int y = Honey.second + dy[i] ;
        if(inside(x , y) && val(mn[x][y] , mn2[x][y]  - time))
            return true ;
    }

    return  false ;
}
int main() {
    cin >> n >> s ;

    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < n ; j++) {
            cin >> a[i][j] ;
            if(a[i][j] == 'M')
                Honey = {i , j} ;
            if(a[i][j] == 'D')
                Home = {i , j} ;
        }
    }

    int l = 0 , r = n * n + 1 ;
    while(l + 1 < r) {
        int m = (l + r) / 2 ;
        if(ok(m))
            l = m ;
        else
            r = m ;
    }
    cout << l - 1 << endl ;
}

Subtask #1
9.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 244 ms 6484 KB Output isn't correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 1 ms 472 KB Output isn't correct
20 Correct 0 ms 348 KB Output is correct
21 Incorrect 1 ms 344 KB Output isn't correct
22 Correct 0 ms 348 KB Output is correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Correct 1 ms 348 KB Output is correct
25 Incorrect 1 ms 348 KB Output isn't correct
26 Correct 1 ms 348 KB Output is correct
27 Incorrect 1 ms 348 KB Output isn't correct
28 Correct 1 ms 348 KB Output is correct
29 Incorrect 2 ms 344 KB Output isn't correct
30 Correct 1 ms 528 KB Output is correct
31 Incorrect 1 ms 348 KB Output isn't correct
32 Correct 1 ms 348 KB Output is correct
33 Incorrect 25 ms 1628 KB Output isn't correct
34 Correct 21 ms 1628 KB Output is correct
35 Incorrect 31 ms 1792 KB Output isn't correct
36 Incorrect 28 ms 2140 KB Output isn't correct
37 Correct 28 ms 2140 KB Output is correct
38 Incorrect 45 ms 2140 KB Output isn't correct
39 Incorrect 36 ms 2396 KB Output isn't correct
40 Correct 35 ms 2392 KB Output is correct
41 Incorrect 51 ms 2396 KB Output isn't correct
42 Incorrect 44 ms 2904 KB Output isn't correct
43 Runtime error 17 ms 5468 KB Execution killed with signal 11
44 Incorrect 65 ms 3016 KB Output isn't correct
45 Incorrect 54 ms 3416 KB Output isn't correct
46 Correct 58 ms 3420 KB Output is correct
47 Incorrect 93 ms 3516 KB Output isn't correct
48 Incorrect 67 ms 3928 KB Output isn't correct
49 Runtime error 22 ms 7512 KB Execution killed with signal 11
50 Incorrect 103 ms 4064 KB Output isn't correct
51 Incorrect 77 ms 4444 KB Output isn't correct
52 Correct 75 ms 4444 KB Output is correct
53 Incorrect 120 ms 4440 KB Output isn't correct
54 Incorrect 94 ms 5276 KB Output isn't correct
55 Correct 91 ms 5204 KB Output is correct
56 Incorrect 143 ms 5204 KB Output isn't correct
57 Incorrect 104 ms 5916 KB Output isn't correct
58 Correct 109 ms 5916 KB Output is correct
59 Incorrect 173 ms 5784 KB Output isn't correct
60 Incorrect 121 ms 6488 KB Output isn't correct
61 Correct 113 ms 6484 KB Output is correct
62 Incorrect 190 ms 6572 KB Output isn't correct
63 Incorrect 258 ms 6480 KB Output isn't correct
64 Runtime error 125 ms 12368 KB Execution killed with signal 11
65 Incorrect 259 ms 6380 KB Output isn't correct
66 Incorrect 257 ms 6480 KB Output isn't correct
67 Incorrect 251 ms 6480 KB Output isn't correct
68 Incorrect 304 ms 6484 KB Output isn't correct
69 Incorrect 287 ms 6480 KB Output isn't correct
70 Incorrect 298 ms 6592 KB Output isn't correct
71 Incorrect 291 ms 6588 KB Output isn't correct
72 Runtime error 180 ms 12472 KB Execution killed with signal 11
73 Incorrect 263 ms 6740 KB Output isn't correct
74 Incorrect 264 ms 6844 KB Output isn't correct
75 Incorrect 274 ms 6740 KB Output isn't correct
76 Incorrect 283 ms 6740 KB Output isn't correct
77 Incorrect 285 ms 6740 KB Output isn't correct
78 Incorrect 242 ms 6812 KB Output isn't correct
79 Incorrect 248 ms 6744 KB Output isn't correct
80 Incorrect 250 ms 6996 KB Output isn't correct
81 Incorrect 239 ms 6740 KB Output isn't correct
82 Incorrect 267 ms 6812 KB Output isn't correct
83 Incorrect 258 ms 6736 KB Output isn't correct
84 Incorrect 250 ms 6712 KB Output isn't correct
85 Incorrect 247 ms 6736 KB Output isn't correct
86 Incorrect 240 ms 6740 KB Output isn't correct
87 Incorrect 243 ms 6736 KB Output isn't correct
88 Incorrect 255 ms 6840 KB Output isn't correct
89 Incorrect 253 ms 6736 KB Output isn't correct
90 Incorrect 253 ms 6992 KB Output isn't correct
91 Incorrect 237 ms 6748 KB Output isn't correct
92 Incorrect 243 ms 6652 KB Output isn't correct