oj.uz

Submission #1071972

# Submission time Handle Problem Language Result Execution time Memory
1071972 2024-08-23T12:54:44 Z 7again Mecho (IOI09_mecho) C++17
11 / 100
 370 ms 12152 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 ;
    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 8 ms 10840 KB Execution killed with signal 11
2 Runtime error 6 ms 10732 KB Execution killed with signal 11
3 Runtime error 6 ms 10844 KB Execution killed with signal 11
4 Runtime error 6 ms 10644 KB Execution killed with signal 11
5 Correct 10 ms 5540 KB Output is correct
6 Runtime error 6 ms 10844 KB Execution killed with signal 11
7 Runtime error 39 ms 11908 KB Execution killed with signal 11
8 Incorrect 11 ms 5524 KB Output isn't correct
9 Correct 12 ms 5556 KB Output is correct
10 Correct 14 ms 5524 KB Output is correct
11 Correct 11 ms 5496 KB Output is correct
12 Runtime error 6 ms 10840 KB Execution killed with signal 11
13 Incorrect 10 ms 5536 KB Output isn't correct
14 Incorrect 11 ms 5564 KB Output isn't correct
15 Runtime error 6 ms 10840 KB Execution killed with signal 11
16 Correct 12 ms 5624 KB Output is correct
17 Runtime error 8 ms 10844 KB Execution killed with signal 11
18 Correct 13 ms 5524 KB Output is correct
19 Runtime error 6 ms 10844 KB Execution killed with signal 11
20 Correct 14 ms 5628 KB Output is correct
21 Runtime error 7 ms 10844 KB Execution killed with signal 11
22 Correct 16 ms 5552 KB Output is correct
23 Runtime error 6 ms 10844 KB Execution killed with signal 11
24 Correct 17 ms 5644 KB Output is correct
25 Runtime error 6 ms 10844 KB Execution killed with signal 11
26 Correct 18 ms 5656 KB Output is correct
27 Runtime error 6 ms 10844 KB Execution killed with signal 11
28 Correct 19 ms 5648 KB Output is correct
29 Runtime error 7 ms 10840 KB Execution killed with signal 11
30 Correct 20 ms 5656 KB Output is correct
31 Runtime error 6 ms 10844 KB Execution killed with signal 11
32 Correct 20 ms 5656 KB Output is correct
33 Runtime error 11 ms 11356 KB Execution killed with signal 11
34 Correct 39 ms 5832 KB Output is correct
35 Correct 56 ms 5832 KB Output is correct
36 Runtime error 13 ms 11352 KB Execution killed with signal 11
37 Correct 51 ms 5856 KB Output is correct
38 Correct 72 ms 5820 KB Output is correct
39 Runtime error 15 ms 11356 KB Execution killed with signal 11
40 Correct 60 ms 5988 KB Output is correct
41 Correct 93 ms 5876 KB Output is correct
42 Runtime error 15 ms 11612 KB Execution killed with signal 11
43 Correct 68 ms 5932 KB Output is correct
44 Correct 103 ms 5884 KB Output is correct
45 Runtime error 17 ms 11592 KB Execution killed with signal 11
46 Correct 77 ms 5936 KB Output is correct
47 Correct 130 ms 5948 KB Output is correct
48 Runtime error 19 ms 11608 KB Execution killed with signal 11
49 Correct 80 ms 5980 KB Output is correct
50 Correct 184 ms 5984 KB Output is correct
51 Runtime error 24 ms 11772 KB Execution killed with signal 11
52 Correct 97 ms 6036 KB Output is correct
53 Correct 187 ms 6032 KB Output is correct
54 Runtime error 25 ms 11864 KB Execution killed with signal 11
55 Correct 110 ms 6036 KB Output is correct
56 Correct 197 ms 6076 KB Output is correct
57 Runtime error 26 ms 11856 KB Execution killed with signal 11
58 Correct 117 ms 6168 KB Output is correct
59 Correct 229 ms 6088 KB Output is correct
60 Runtime error 28 ms 11856 KB Execution killed with signal 11
61 Runtime error 39 ms 11884 KB Execution killed with signal 11
62 Runtime error 112 ms 11872 KB Execution killed with signal 11
63 Runtime error 145 ms 11944 KB Execution killed with signal 11
64 Runtime error 158 ms 11908 KB Execution killed with signal 11
65 Runtime error 126 ms 12024 KB Execution killed with signal 11
66 Runtime error 140 ms 12052 KB Execution killed with signal 11
67 Runtime error 130 ms 11884 KB Execution killed with signal 11
68 Runtime error 242 ms 12124 KB Execution killed with signal 11
69 Runtime error 250 ms 11992 KB Execution killed with signal 11
70 Runtime error 258 ms 12012 KB Execution killed with signal 11
71 Runtime error 275 ms 12016 KB Execution killed with signal 11
72 Runtime error 221 ms 11956 KB Execution killed with signal 11
73 Runtime error 274 ms 12124 KB Execution killed with signal 11
74 Runtime error 40 ms 12116 KB Execution killed with signal 11
75 Runtime error 39 ms 12152 KB Execution killed with signal 11
76 Runtime error 36 ms 12116 KB Execution killed with signal 11
77 Runtime error 41 ms 12112 KB Execution killed with signal 11
78 Incorrect 308 ms 6144 KB Output isn't correct
79 Correct 278 ms 6156 KB Output is correct
80 Correct 288 ms 6152 KB Output is correct
81 Correct 297 ms 6148 KB Output is correct
82 Correct 292 ms 6144 KB Output is correct
83 Runtime error 165 ms 12032 KB Execution killed with signal 11
84 Correct 328 ms 6060 KB Output is correct
85 Correct 332 ms 6116 KB Output is correct
86 Correct 332 ms 6136 KB Output is correct
87 Correct 300 ms 6136 KB Output is correct
88 Runtime error 162 ms 11936 KB Execution killed with signal 11
89 Correct 323 ms 6152 KB Output is correct
90 Correct 329 ms 6136 KB Output is correct
91 Correct 370 ms 6140 KB Output is correct
92 Correct 301 ms 6140 KB Output is correct