oj.uz

Submission #1072159

# Submission time Handle Problem Language Result Execution time Memory
1072159 2024-08-23T15:05:05 Z 7again Mecho (IOI09_mecho) C++17
5 / 100
 348 ms 12796 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 << endl ;
}

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Runtime error 0 ms 348 KB Execution killed with signal 11
3 Runtime error 0 ms 348 KB Execution killed with signal 11
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Correct 0 ms 348 KB Output is correct
6 Runtime error 0 ms 348 KB Execution killed with signal 11
7 Runtime error 348 ms 12584 KB Execution killed with signal 11
8 Runtime error 1 ms 600 KB Execution killed with signal 11
9 Runtime error 1 ms 348 KB Execution killed with signal 11
10 Runtime error 1 ms 348 KB Execution killed with signal 11
11 Runtime error 0 ms 604 KB Execution killed with signal 11
12 Runtime error 1 ms 604 KB Execution killed with signal 11
13 Correct 1 ms 344 KB Output is 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 1 ms 604 KB Execution killed with signal 11
17 Runtime error 1 ms 604 KB Execution killed with signal 11
18 Runtime error 1 ms 604 KB Execution killed with signal 11
19 Runtime error 1 ms 484 KB Execution killed with signal 11
20 Runtime error 1 ms 604 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 600 KB Execution killed with signal 11
25 Runtime error 1 ms 604 KB Execution killed with signal 11
26 Runtime error 2 ms 700 KB Execution killed with signal 11
27 Runtime error 1 ms 600 KB Execution killed with signal 11
28 Runtime error 1 ms 604 KB Execution killed with signal 11
29 Runtime error 1 ms 704 KB Execution killed with signal 11
30 Runtime error 2 ms 724 KB Execution killed with signal 11
31 Runtime error 1 ms 700 KB Execution killed with signal 11
32 Runtime error 2 ms 600 KB Execution killed with signal 11
33 Runtime error 9 ms 3080 KB Execution killed with signal 11
34 Runtime error 14 ms 2996 KB Execution killed with signal 11
35 Runtime error 21 ms 3072 KB Execution killed with signal 11
36 Runtime error 10 ms 3780 KB Execution killed with signal 11
37 Runtime error 11 ms 3716 KB Execution killed with signal 11
38 Runtime error 48 ms 3888 KB Execution killed with signal 11
39 Runtime error 14 ms 4752 KB Execution killed with signal 11
40 Runtime error 23 ms 4548 KB Execution killed with signal 11
41 Runtime error 44 ms 4692 KB Execution killed with signal 11
42 Runtime error 15 ms 5648 KB Execution killed with signal 11
43 Runtime error 25 ms 5548 KB Execution killed with signal 11
44 Runtime error 42 ms 5540 KB Execution killed with signal 11
45 Runtime error 18 ms 6520 KB Execution killed with signal 11
46 Runtime error 20 ms 6556 KB Execution killed with signal 11
47 Runtime error 98 ms 6452 KB Execution killed with signal 11
48 Runtime error 22 ms 7584 KB Execution killed with signal 11
49 Runtime error 23 ms 7672 KB Execution killed with signal 11
50 Runtime error 68 ms 7524 KB Execution killed with signal 11
51 Runtime error 28 ms 8612 KB Execution killed with signal 11
52 Runtime error 29 ms 8760 KB Execution killed with signal 11
53 Runtime error 91 ms 8680 KB Execution killed with signal 11
54 Runtime error 30 ms 9896 KB Execution killed with signal 11
55 Runtime error 35 ms 9972 KB Execution killed with signal 11
56 Runtime error 135 ms 9964 KB Execution killed with signal 11
57 Runtime error 30 ms 11128 KB Execution killed with signal 11
58 Runtime error 48 ms 11208 KB Execution killed with signal 11
59 Runtime error 108 ms 11332 KB Execution killed with signal 11
60 Runtime error 42 ms 12556 KB Execution killed with signal 11
61 Runtime error 43 ms 12596 KB Execution killed with signal 11
62 Runtime error 146 ms 12556 KB Execution killed with signal 11
63 Runtime error 178 ms 12540 KB Execution killed with signal 11
64 Incorrect 300 ms 6760 KB Output isn't correct
65 Runtime error 136 ms 12640 KB Execution killed with signal 11
66 Runtime error 141 ms 12548 KB Execution killed with signal 11
67 Runtime error 174 ms 12516 KB Execution killed with signal 11
68 Incorrect 311 ms 6764 KB Output isn't correct
69 Incorrect 311 ms 6740 KB Output isn't correct
70 Incorrect 302 ms 6752 KB Output isn't correct
71 Incorrect 299 ms 6748 KB Output isn't correct
72 Runtime error 223 ms 12612 KB Execution killed with signal 11
73 Runtime error 295 ms 12748 KB Execution killed with signal 11
74 Runtime error 181 ms 12680 KB Execution killed with signal 11
75 Runtime error 182 ms 12696 KB Execution killed with signal 11
76 Runtime error 176 ms 12620 KB Execution killed with signal 11
77 Runtime error 175 ms 12724 KB Execution killed with signal 11
78 Incorrect 287 ms 6764 KB Output isn't correct
79 Incorrect 277 ms 6796 KB Output isn't correct
80 Incorrect 265 ms 6780 KB Output isn't correct
81 Incorrect 270 ms 6908 KB Output isn't correct
82 Incorrect 271 ms 6784 KB Output isn't correct
83 Runtime error 172 ms 12796 KB Execution killed with signal 11
84 Incorrect 271 ms 6788 KB Output isn't correct
85 Incorrect 304 ms 6776 KB Output isn't correct
86 Incorrect 266 ms 6776 KB Output isn't correct
87 Incorrect 300 ms 6784 KB Output isn't correct
88 Runtime error 170 ms 12684 KB Execution killed with signal 11
89 Incorrect 263 ms 6780 KB Output isn't correct
90 Incorrect 263 ms 6872 KB Output isn't correct
91 Incorrect 269 ms 6788 KB Output isn't correct
92 Incorrect 288 ms 6780 KB Output isn't correct