oj.uz

Submission #1072023

# Submission time Handle Problem Language Result Execution time Memory
1072023 2024-08-23T13:27:18 Z 7again Mecho (IOI09_mecho) C++17
5 / 100
 342 ms 12144 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}) ;
            }
        }
    }
    if(mn[Home.first][Home.second] == 1e9)
        return  0 ;
    return  1 ;
}
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 1 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 1 ms 348 KB Execution killed with signal 11
7 Runtime error 181 ms 12068 KB Execution killed with signal 11
8 Runtime error 1 ms 604 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 1 ms 348 KB Execution killed with signal 11
12 Runtime error 1 ms 604 KB Execution killed with signal 11
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Runtime error 0 ms 348 KB Execution killed with signal 11
16 Runtime error 1 ms 348 KB Execution killed with signal 11
17 Runtime error 0 ms 604 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 604 KB Execution killed with signal 11
21 Runtime error 0 ms 604 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 604 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 3100 KB Execution killed with signal 11
34 Runtime error 9 ms 2996 KB Execution killed with signal 11
35 Runtime error 21 ms 3012 KB Execution killed with signal 11
36 Runtime error 9 ms 3800 KB Execution killed with signal 11
37 Runtime error 10 ms 3552 KB Execution killed with signal 11
38 Runtime error 30 ms 3704 KB Execution killed with signal 11
39 Runtime error 13 ms 4496 KB Execution killed with signal 11
40 Runtime error 14 ms 4548 KB Execution killed with signal 11
41 Runtime error 39 ms 4520 KB Execution killed with signal 11
42 Runtime error 15 ms 5388 KB Execution killed with signal 11
43 Runtime error 17 ms 5312 KB Execution killed with signal 11
44 Runtime error 42 ms 5164 KB Execution killed with signal 11
45 Runtime error 17 ms 6268 KB Execution killed with signal 11
46 Runtime error 18 ms 6080 KB Execution killed with signal 11
47 Runtime error 71 ms 6232 KB Execution killed with signal 11
48 Runtime error 20 ms 7080 KB Execution killed with signal 11
49 Runtime error 25 ms 7156 KB Execution killed with signal 11
50 Runtime error 88 ms 7224 KB Execution killed with signal 11
51 Runtime error 23 ms 8256 KB Execution killed with signal 11
52 Runtime error 27 ms 8204 KB Execution killed with signal 11
53 Runtime error 87 ms 8372 KB Execution killed with signal 11
54 Runtime error 28 ms 9376 KB Execution killed with signal 11
55 Runtime error 30 ms 9412 KB Execution killed with signal 11
56 Runtime error 92 ms 9456 KB Execution killed with signal 11
57 Runtime error 31 ms 10616 KB Execution killed with signal 11
58 Runtime error 36 ms 10644 KB Execution killed with signal 11
59 Runtime error 116 ms 10784 KB Execution killed with signal 11
60 Runtime error 34 ms 12044 KB Execution killed with signal 11
61 Runtime error 39 ms 12048 KB Execution killed with signal 11
62 Runtime error 120 ms 11900 KB Execution killed with signal 11
63 Runtime error 138 ms 11952 KB Execution killed with signal 11
64 Runtime error 186 ms 11872 KB Execution killed with signal 11
65 Runtime error 124 ms 11880 KB Execution killed with signal 11
66 Runtime error 140 ms 12056 KB Execution killed with signal 11
67 Runtime error 130 ms 11904 KB Execution killed with signal 11
68 Runtime error 242 ms 12144 KB Execution killed with signal 11
69 Runtime error 252 ms 12096 KB Execution killed with signal 11
70 Runtime error 258 ms 12096 KB Execution killed with signal 11
71 Runtime error 275 ms 12052 KB Execution killed with signal 11
72 Runtime error 252 ms 12112 KB Execution killed with signal 11
73 Runtime error 315 ms 11940 KB Execution killed with signal 11
74 Runtime error 207 ms 12088 KB Execution killed with signal 11
75 Runtime error 174 ms 12136 KB Execution killed with signal 11
76 Runtime error 172 ms 12108 KB Execution killed with signal 11
77 Runtime error 179 ms 12064 KB Execution killed with signal 11
78 Incorrect 297 ms 6148 KB Output isn't correct
79 Correct 282 ms 6124 KB Output is correct
80 Correct 287 ms 6392 KB Output is correct
81 Correct 290 ms 6156 KB Output is correct
82 Correct 298 ms 6116 KB Output is correct
83 Runtime error 166 ms 12032 KB Execution killed with signal 11
84 Correct 319 ms 6056 KB Output is correct
85 Correct 342 ms 6120 KB Output is correct
86 Correct 320 ms 6160 KB Output is correct
87 Correct 308 ms 6160 KB Output is correct
88 Runtime error 165 ms 11928 KB Execution killed with signal 11
89 Correct 327 ms 6128 KB Output is correct
90 Correct 324 ms 6136 KB Output is correct
91 Correct 308 ms 6152 KB Output is correct
92 Correct 327 ms 6020 KB Output is correct