oj.uz

Submission #1071968

# Submission time Handle Problem Language Result Execution time Memory
1071968 2024-08-23T12:50:24 Z 7again Mecho (IOI09_mecho) C++17
2 / 100
 390 ms 12148 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
2.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 1 ms 420 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 38 ms 12148 KB Execution killed with signal 11
8 Runtime error 1 ms 344 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 348 KB Execution killed with signal 11
12 Runtime error 1 ms 604 KB Execution killed with signal 11
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 2 ms 516 KB Output isn't correct
15 Runtime error 1 ms 604 KB Execution killed with signal 11
16 Runtime error 0 ms 348 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 604 KB Execution killed with signal 11
20 Runtime error 0 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 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 600 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 2960 KB Execution killed with signal 11
34 Runtime error 8 ms 2996 KB Execution killed with signal 11
35 Runtime error 22 ms 2860 KB Execution killed with signal 11
36 Runtime error 8 ms 3676 KB Execution killed with signal 11
37 Runtime error 10 ms 3668 KB Execution killed with signal 11
38 Runtime error 30 ms 3776 KB Execution killed with signal 11
39 Runtime error 11 ms 4440 KB Execution killed with signal 11
40 Runtime error 14 ms 4548 KB Execution killed with signal 11
41 Runtime error 41 ms 4540 KB Execution killed with signal 11
42 Runtime error 12 ms 5212 KB Execution killed with signal 11
43 Runtime error 17 ms 5316 KB Execution killed with signal 11
44 Runtime error 52 ms 5264 KB Execution killed with signal 11
45 Runtime error 16 ms 6232 KB Execution killed with signal 11
46 Runtime error 20 ms 6044 KB Execution killed with signal 11
47 Runtime error 70 ms 6120 KB Execution killed with signal 11
48 Runtime error 21 ms 7256 KB Execution killed with signal 11
49 Runtime error 23 ms 7164 KB Execution killed with signal 11
50 Runtime error 65 ms 7160 KB Execution killed with signal 11
51 Runtime error 24 ms 8284 KB Execution killed with signal 11
52 Runtime error 30 ms 8276 KB Execution killed with signal 11
53 Runtime error 88 ms 8400 KB Execution killed with signal 11
54 Runtime error 23 ms 9564 KB Execution killed with signal 11
55 Runtime error 32 ms 9548 KB Execution killed with signal 11
56 Runtime error 91 ms 9452 KB Execution killed with signal 11
57 Runtime error 36 ms 10576 KB Execution killed with signal 11
58 Runtime error 36 ms 10644 KB Execution killed with signal 11
59 Runtime error 106 ms 10552 KB Execution killed with signal 11
60 Runtime error 30 ms 11860 KB Execution killed with signal 11
61 Runtime error 49 ms 11960 KB Execution killed with signal 11
62 Runtime error 113 ms 12080 KB Execution killed with signal 11
63 Runtime error 149 ms 12064 KB Execution killed with signal 11
64 Runtime error 160 ms 11912 KB Execution killed with signal 11
65 Runtime error 126 ms 12020 KB Execution killed with signal 11
66 Runtime error 143 ms 11944 KB Execution killed with signal 11
67 Runtime error 128 ms 12084 KB Execution killed with signal 11
68 Runtime error 247 ms 11960 KB Execution killed with signal 11
69 Runtime error 258 ms 11996 KB Execution killed with signal 11
70 Runtime error 267 ms 12092 KB Execution killed with signal 11
71 Runtime error 281 ms 11992 KB Execution killed with signal 11
72 Runtime error 224 ms 11940 KB Execution killed with signal 11
73 Runtime error 288 ms 12140 KB Execution killed with signal 11
74 Runtime error 39 ms 11960 KB Execution killed with signal 11
75 Runtime error 38 ms 12052 KB Execution killed with signal 11
76 Runtime error 40 ms 12112 KB Execution killed with signal 11
77 Runtime error 40 ms 12112 KB Execution killed with signal 11
78 Incorrect 311 ms 6144 KB Output isn't correct
79 Correct 290 ms 6152 KB Output is correct
80 Correct 324 ms 6128 KB Output is correct
81 Correct 301 ms 6144 KB Output is correct
82 Correct 298 ms 6160 KB Output is correct
83 Runtime error 164 ms 11992 KB Execution killed with signal 11
84 Correct 330 ms 6052 KB Output is correct
85 Correct 390 ms 6112 KB Output is correct
86 Correct 326 ms 6264 KB Output is correct
87 Correct 305 ms 6144 KB Output is correct
88 Runtime error 165 ms 11932 KB Execution killed with signal 11
89 Correct 345 ms 6152 KB Output is correct
90 Correct 356 ms 6144 KB Output is correct
91 Correct 315 ms 6348 KB Output is correct
92 Correct 309 ms 6020 KB Output is correct