oj.uz

Submission #1072020

# Submission time Handle Problem Language Result Execution time Memory
1072020 2024-08-23T13:25:43 Z 7again Mecho (IOI09_mecho) C++17
14 / 100
 368 ms 12184 KB 
#include <bits/stdc++.h>

using namespace std ;

const int N = 801 ;
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
14.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 10676 KB Execution killed with signal 11
2 Runtime error 7 ms 10760 KB Execution killed with signal 11
3 Runtime error 8 ms 10872 KB Execution killed with signal 11
4 Runtime error 8 ms 10680 KB Execution killed with signal 11
5 Correct 8 ms 5532 KB Output is correct
6 Runtime error 11 ms 10856 KB Execution killed with signal 11
7 Runtime error 188 ms 11980 KB Execution killed with signal 11
8 Incorrect 11 ms 5496 KB Output isn't correct
9 Correct 13 ms 5620 KB Output is correct
10 Correct 12 ms 5572 KB Output is correct
11 Correct 11 ms 5496 KB Output is correct
12 Runtime error 19 ms 11020 KB Execution killed with signal 11
13 Correct 11 ms 5564 KB Output is correct
14 Incorrect 10 ms 5560 KB Output isn't correct
15 Runtime error 7 ms 10760 KB Execution killed with signal 11
16 Correct 12 ms 5592 KB Output is correct
17 Runtime error 7 ms 10760 KB Execution killed with signal 11
18 Correct 14 ms 5592 KB Output is correct
19 Runtime error 8 ms 10756 KB Execution killed with signal 11
20 Correct 15 ms 5556 KB Output is correct
21 Runtime error 7 ms 10936 KB Execution killed with signal 11
22 Correct 21 ms 5796 KB Output is correct
23 Runtime error 7 ms 10760 KB Execution killed with signal 11
24 Correct 16 ms 5592 KB Output is correct
25 Runtime error 7 ms 10760 KB Execution killed with signal 11
26 Correct 17 ms 5604 KB Output is correct
27 Runtime error 7 ms 10760 KB Execution killed with signal 11
28 Correct 18 ms 5688 KB Output is correct
29 Runtime error 7 ms 10760 KB Execution killed with signal 11
30 Correct 20 ms 5692 KB Output is correct
31 Runtime error 7 ms 11012 KB Execution killed with signal 11
32 Correct 20 ms 5604 KB Output is correct
33 Runtime error 14 ms 11272 KB Execution killed with signal 11
34 Correct 40 ms 5848 KB Output is correct
35 Correct 61 ms 5880 KB Output is correct
36 Runtime error 14 ms 11272 KB Execution killed with signal 11
37 Correct 51 ms 5856 KB Output is correct
38 Correct 66 ms 5852 KB Output is correct
39 Runtime error 16 ms 11524 KB Execution killed with signal 11
40 Correct 57 ms 5896 KB Output is correct
41 Correct 95 ms 5884 KB Output is correct
42 Runtime error 19 ms 11528 KB Execution killed with signal 11
43 Correct 65 ms 5964 KB Output is correct
44 Correct 101 ms 5908 KB Output is correct
45 Runtime error 20 ms 11516 KB Execution killed with signal 11
46 Correct 79 ms 5956 KB Output is correct
47 Correct 122 ms 5944 KB Output is correct
48 Runtime error 22 ms 11784 KB Execution killed with signal 11
49 Correct 85 ms 5984 KB Output is correct
50 Correct 153 ms 6024 KB Output is correct
51 Runtime error 25 ms 11680 KB Execution killed with signal 11
52 Correct 96 ms 6036 KB Output is correct
53 Correct 199 ms 6024 KB Output is correct
54 Runtime error 28 ms 11732 KB Execution killed with signal 11
55 Correct 111 ms 6124 KB Output is correct
56 Correct 195 ms 6060 KB Output is correct
57 Runtime error 35 ms 11900 KB Execution killed with signal 11
58 Correct 131 ms 6068 KB Output is correct
59 Correct 221 ms 6092 KB Output is correct
60 Runtime error 35 ms 12032 KB Execution killed with signal 11
61 Correct 142 ms 6140 KB Output is correct
62 Correct 255 ms 6124 KB Output is correct
63 Runtime error 204 ms 12104 KB Execution killed with signal 11
64 Runtime error 160 ms 12100 KB Execution killed with signal 11
65 Runtime error 174 ms 12104 KB Execution killed with signal 11
66 Runtime error 171 ms 12068 KB Execution killed with signal 11
67 Runtime error 216 ms 12104 KB Execution killed with signal 11
68 Runtime error 248 ms 12044 KB Execution killed with signal 11
69 Runtime error 242 ms 11940 KB Execution killed with signal 11
70 Runtime error 255 ms 12068 KB Execution killed with signal 11
71 Correct 316 ms 6136 KB Output is correct
72 Correct 295 ms 6152 KB Output is correct
73 Correct 282 ms 6156 KB Output is correct
74 Runtime error 170 ms 12124 KB Execution killed with signal 11
75 Runtime error 175 ms 12072 KB Execution killed with signal 11
76 Runtime error 175 ms 12028 KB Execution killed with signal 11
77 Runtime error 180 ms 12044 KB Execution killed with signal 11
78 Incorrect 292 ms 6148 KB Output isn't correct
79 Correct 292 ms 6160 KB Output is correct
80 Correct 292 ms 6164 KB Output is correct
81 Correct 316 ms 6152 KB Output is correct
82 Correct 337 ms 6160 KB Output is correct
83 Runtime error 183 ms 12184 KB Execution killed with signal 11
84 Correct 336 ms 6036 KB Output is correct
85 Correct 332 ms 6388 KB Output is correct
86 Correct 345 ms 6160 KB Output is correct
87 Correct 320 ms 6172 KB Output is correct
88 Runtime error 164 ms 12016 KB Execution killed with signal 11
89 Correct 368 ms 6148 KB Output is correct
90 Correct 350 ms 6152 KB Output is correct
91 Correct 339 ms 6156 KB Output is correct
92 Correct 345 ms 6096 KB Output is correct