oj.uz

Submission #1071970

# Submission time Handle Problem Language Result Execution time Memory
1071970 2024-08-23T12:53:16 Z 7again Mecho (IOI09_mecho) C++17
11 / 100
 327 ms 12180 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 + 1 , vector<int>(n + 1 , 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 + 1 , vector<int>(n + 1 , 1e9)) ;
    queue <pair <int , int>> q ;
    mn[Honey.first][Honey.second] = 0 ;
    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
11.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 344 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 0 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 36 ms 12120 KB Execution killed with signal 11
8 Incorrect 0 ms 348 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
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 Correct 0 ms 348 KB Output is correct
17 Runtime error 1 ms 604 KB Execution killed with signal 11
18 Correct 0 ms 348 KB Output is correct
19 Runtime error 1 ms 604 KB Execution killed with signal 11
20 Correct 0 ms 348 KB Output is correct
21 Runtime error 1 ms 604 KB Execution killed with signal 11
22 Correct 0 ms 348 KB Output is correct
23 Runtime error 1 ms 604 KB Execution killed with signal 11
24 Correct 1 ms 348 KB Output is correct
25 Runtime error 1 ms 604 KB Execution killed with signal 11
26 Correct 1 ms 348 KB Output is correct
27 Runtime error 1 ms 604 KB Execution killed with signal 11
28 Correct 1 ms 348 KB Output is correct
29 Runtime error 1 ms 604 KB Execution killed with signal 11
30 Correct 1 ms 348 KB Output is correct
31 Runtime error 1 ms 604 KB Execution killed with signal 11
32 Correct 1 ms 348 KB Output is correct
33 Runtime error 6 ms 2908 KB Execution killed with signal 11
34 Correct 25 ms 1696 KB Output is correct
35 Correct 45 ms 1700 KB Output is correct
36 Runtime error 8 ms 3676 KB Execution killed with signal 11
37 Correct 33 ms 2096 KB Output is correct
38 Correct 59 ms 1880 KB Output is correct
39 Runtime error 9 ms 4440 KB Execution killed with signal 11
40 Correct 43 ms 2396 KB Output is correct
41 Correct 80 ms 2408 KB Output is correct
42 Runtime error 12 ms 5224 KB Execution killed with signal 11
43 Correct 53 ms 2824 KB Output is correct
44 Correct 96 ms 2800 KB Output is correct
45 Runtime error 14 ms 6236 KB Execution killed with signal 11
46 Correct 66 ms 3276 KB Output is correct
47 Correct 112 ms 3272 KB Output is correct
48 Runtime error 17 ms 7260 KB Execution killed with signal 11
49 Correct 72 ms 3784 KB Output is correct
50 Correct 144 ms 3780 KB Output is correct
51 Runtime error 20 ms 8284 KB Execution killed with signal 11
52 Correct 90 ms 4332 KB Output is correct
53 Correct 171 ms 4300 KB Output is correct
54 Runtime error 23 ms 9552 KB Execution killed with signal 11
55 Correct 103 ms 4908 KB Output is correct
56 Correct 198 ms 4856 KB Output is correct
57 Runtime error 41 ms 10580 KB Execution killed with signal 11
58 Correct 118 ms 5480 KB Output is correct
59 Correct 222 ms 5492 KB Output is correct
60 Runtime error 28 ms 11864 KB Execution killed with signal 11
61 Correct 142 ms 6144 KB Output is correct
62 Correct 258 ms 6128 KB Output is correct
63 Runtime error 202 ms 12100 KB Execution killed with signal 11
64 Runtime error 157 ms 12056 KB Execution killed with signal 11
65 Runtime error 180 ms 12068 KB Execution killed with signal 11
66 Runtime error 170 ms 12064 KB Execution killed with signal 11
67 Runtime error 211 ms 12052 KB Execution killed with signal 11
68 Runtime error 251 ms 12084 KB Execution killed with signal 11
69 Runtime error 248 ms 11944 KB Execution killed with signal 11
70 Runtime error 261 ms 12068 KB Execution killed with signal 11
71 Correct 319 ms 6096 KB Output is correct
72 Incorrect 309 ms 6136 KB Output isn't correct
73 Incorrect 299 ms 6140 KB Output isn't correct
74 Runtime error 36 ms 12112 KB Execution killed with signal 11
75 Runtime error 40 ms 12112 KB Execution killed with signal 11
76 Runtime error 39 ms 12112 KB Execution killed with signal 11
77 Runtime error 43 ms 12112 KB Execution killed with signal 11
78 Incorrect 313 ms 6132 KB Output isn't correct
79 Correct 288 ms 6164 KB Output is correct
80 Correct 284 ms 6144 KB Output is correct
81 Correct 293 ms 6160 KB Output is correct
82 Correct 301 ms 6120 KB Output is correct
83 Runtime error 160 ms 12096 KB Execution killed with signal 11
84 Correct 316 ms 6168 KB Output is correct
85 Correct 325 ms 6148 KB Output is correct
86 Correct 322 ms 6144 KB Output is correct
87 Correct 320 ms 6168 KB Output is correct
88 Runtime error 163 ms 12180 KB Execution killed with signal 11
89 Correct 325 ms 6152 KB Output is correct
90 Correct 327 ms 6148 KB Output is correct
91 Correct 311 ms 6156 KB Output is correct
92 Correct 303 ms 6104 KB Output is correct