oj.uz

Submission #1072160

# Submission time Handle Problem Language Result Execution time Memory
1072160 2024-08-23T15:05:25 Z 7again Mecho (IOI09_mecho) C++17
0 / 100
 311 ms 12224 KB 
#include <bits/stdc++.h>

using namespace std ;

const int N = 800 ;
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 ;
}
bool ok(int time) {

    vector<vector<int>> mn2(n , vector<int>(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}) ;
            }
        }
    }

    vector<vector<int>> mn(n , vector<int>(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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 KB Execution killed with signal 11
2 Runtime error 0 ms 348 KB Execution killed with signal 11
3 Runtime error 1 ms 348 KB Execution killed with signal 11
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Incorrect 0 ms 348 KB Output isn't correct
6 Runtime error 0 ms 348 KB Execution killed with signal 11
7 Runtime error 249 ms 12056 KB Execution killed with signal 11
8 Runtime error 1 ms 600 KB Execution killed with signal 11
9 Runtime error 0 ms 348 KB Execution killed with signal 11
10 Runtime error 0 ms 348 KB Execution killed with signal 11
11 Runtime error 0 ms 348 KB Execution killed with signal 11
12 Runtime error 1 ms 604 KB Execution killed with signal 11
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Runtime error 0 ms 604 KB Execution killed with signal 11
16 Runtime error 0 ms 604 KB Execution killed with signal 11
17 Runtime error 1 ms 600 KB Execution killed with signal 11
18 Runtime error 0 ms 604 KB Execution killed with signal 11
19 Runtime error 0 ms 604 KB Execution killed with signal 11
20 Runtime error 1 ms 856 KB Execution killed with signal 11
21 Runtime error 1 ms 600 KB Execution killed with signal 11
22 Runtime error 1 ms 604 KB Execution killed with signal 11
23 Runtime error 1 ms 604 KB Execution killed with signal 11
24 Runtime error 1 ms 604 KB Execution killed with signal 11
25 Runtime error 1 ms 604 KB Execution killed with signal 11
26 Runtime error 1 ms 492 KB Execution killed with signal 11
27 Runtime error 1 ms 604 KB Execution killed with signal 11
28 Runtime error 1 ms 604 KB Execution killed with signal 11
29 Runtime error 1 ms 604 KB Execution killed with signal 11
30 Runtime error 1 ms 604 KB Execution killed with signal 11
31 Runtime error 1 ms 604 KB Execution killed with signal 11
32 Runtime error 1 ms 604 KB Execution killed with signal 11
33 Runtime error 7 ms 3044 KB Execution killed with signal 11
34 Runtime error 10 ms 2996 KB Execution killed with signal 11
35 Runtime error 21 ms 3056 KB Execution killed with signal 11
36 Runtime error 11 ms 3784 KB Execution killed with signal 11
37 Runtime error 11 ms 3668 KB Execution killed with signal 11
38 Runtime error 27 ms 3592 KB Execution killed with signal 11
39 Runtime error 12 ms 4492 KB Execution killed with signal 11
40 Runtime error 15 ms 4544 KB Execution killed with signal 11
41 Runtime error 43 ms 4444 KB Execution killed with signal 11
42 Runtime error 14 ms 5388 KB Execution killed with signal 11
43 Runtime error 16 ms 5316 KB Execution killed with signal 11
44 Runtime error 42 ms 5288 KB Execution killed with signal 11
45 Runtime error 17 ms 6264 KB Execution killed with signal 11
46 Runtime error 19 ms 6300 KB Execution killed with signal 11
47 Runtime error 90 ms 6140 KB Execution killed with signal 11
48 Runtime error 23 ms 7084 KB Execution killed with signal 11
49 Runtime error 23 ms 7196 KB Execution killed with signal 11
50 Runtime error 64 ms 7152 KB Execution killed with signal 11
51 Runtime error 23 ms 8392 KB Execution killed with signal 11
52 Runtime error 27 ms 8208 KB Execution killed with signal 11
53 Runtime error 85 ms 8300 KB Execution killed with signal 11
54 Runtime error 27 ms 9376 KB Execution killed with signal 11
55 Runtime error 30 ms 9468 KB Execution killed with signal 11
56 Runtime error 87 ms 9380 KB Execution killed with signal 11
57 Runtime error 31 ms 10616 KB Execution killed with signal 11
58 Runtime error 36 ms 10648 KB Execution killed with signal 11
59 Runtime error 99 ms 10540 KB Execution killed with signal 11
60 Runtime error 36 ms 12040 KB Execution killed with signal 11
61 Runtime error 40 ms 12224 KB Execution killed with signal 11
62 Runtime error 112 ms 12008 KB Execution killed with signal 11
63 Runtime error 144 ms 12052 KB Execution killed with signal 11
64 Incorrect 261 ms 6120 KB Output isn't correct
65 Runtime error 128 ms 12056 KB Execution killed with signal 11
66 Runtime error 145 ms 12056 KB Execution killed with signal 11
67 Runtime error 124 ms 11900 KB Execution killed with signal 11
68 Incorrect 295 ms 6124 KB Output isn't correct
69 Incorrect 300 ms 6300 KB Output isn't correct
70 Incorrect 299 ms 6124 KB Output isn't correct
71 Incorrect 311 ms 6132 KB Output isn't correct
72 Runtime error 215 ms 11900 KB Execution killed with signal 11
73 Runtime error 290 ms 11940 KB Execution killed with signal 11
74 Runtime error 182 ms 12096 KB Execution killed with signal 11
75 Runtime error 176 ms 12140 KB Execution killed with signal 11
76 Runtime error 172 ms 12032 KB Execution killed with signal 11
77 Runtime error 180 ms 12116 KB Execution killed with signal 11
78 Incorrect 257 ms 6156 KB Output isn't correct
79 Incorrect 262 ms 6132 KB Output isn't correct
80 Incorrect 263 ms 6168 KB Output isn't correct
81 Incorrect 268 ms 6152 KB Output isn't correct
82 Incorrect 269 ms 6152 KB Output isn't correct
83 Runtime error 163 ms 12028 KB Execution killed with signal 11
84 Incorrect 268 ms 6100 KB Output isn't correct
85 Incorrect 276 ms 6228 KB Output isn't correct
86 Incorrect 262 ms 6124 KB Output isn't correct
87 Incorrect 270 ms 6140 KB Output isn't correct
88 Runtime error 170 ms 12140 KB Execution killed with signal 11
89 Incorrect 263 ms 6140 KB Output isn't correct
90 Incorrect 283 ms 6132 KB Output isn't correct
91 Incorrect 262 ms 6152 KB Output isn't correct
92 Incorrect 259 ms 6140 KB Output isn't correct