oj.uz

Submission #103693

# Submission time Handle Problem Language Result Execution time Memory
103693 2019-04-02T04:42:51 Z Badral Mecho (IOI09_mecho) C++17
10 / 100
 512 ms 66560 KB 
#include<bits/stdc++.h>

using namespace std;

char a[1015][1015];
int bear[1105][1015];
int bee[1105][1015];
struct point{
    int x, y;
};
point mep(int a, int b) {point x; x.x = a; x.y = b; return x;}
int x = -1, y = -1;
int xxx = -1, yyy = -1;
    int n;
    int kk;
bool can(int k) {
    memset(bear, 0, sizeof bear);
    bear[x][y] = k*k;
    queue<point> q;
    q.push(mep(x, y));
    while(!q.empty()) {
        int x = q.front().x, y = q.front().y;
        q.pop();
        if( x < n && bear[x+1][y] == 0 && (a[x+1][y] == 'G' || a[x+1][y] == 'D') && bee[x+1][y] > (bear[x][y]+1)) {bear[x+1][y] = bear[x][y] + 1;q.push(mep(x+1, y));}
        if( x > 1 && bear[x-1][y] == 0 && (a[x-1][y] == 'G' || a[x-1][y] == 'D') && bee[x-1][y] > (bear[x][y]+1)) {bear[x-1][y] = bear[x][y] + 1;q.push(mep(x-1, y));}
        if( y < n && bear[x][y+1] == 0 && (a[x][y+1] == 'G' || a[x][y+1] == 'D') && bee[x][y+1] > (bear[x][y]+1)) {bear[x][y+1] = bear[x][y] + 1;q.push(mep(x, y+1));}
        if( y > 1 && bear[x][y-1] == 0 && (a[x][y-1] == 'G' || a[x][y-1] == 'D') && bee[x][y-1] > (bear[x][y]+1)) {bear[x][y-1] = bear[x][y] + 1;q.push(mep(x, y-1));}
    }
    // for(int i = 1; i <= n; i++) {
    //     for(int j = 1; j<= n; j++) {
    //         cout<<bear[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    return bear[xxx][yyy] != 0;  
}
int main() {
    cin >>n;
    cin >>kk;
    queue<point> p;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            bee[i][j] = INT_MAX; 
            cin >>a[i][j];
            if(a[i][j] == 'H') {p.push(mep(i, j));bee[i][j] = 0;}
            if(a[i][j] == 'M') {x = i; y = j;}
            if(a[i][j] == 'D') {xxx = i; yyy = j;}
        }
    }

    while(!p.empty()) {
        int x = p.front().x, y = p.front().y;
        p.pop();
        if(x < n && bee[x+1][y] > bee[x][y] + 1 && (a[x+1][y] != 'T' && a[x+1][y] != 'D')) {bee[x+1][y] = bee[x][y] + kk; p.push(mep(x+1, y));}
        if(x > 1 && bee[x-1][y] > bee[x][y] + 1 && (a[x-1][y] != 'T' && a[x-1][y] != 'D')) {bee[x-1][y] = bee[x][y] + kk; p.push(mep(x-1, y));}
        if(y < n && bee[x][y+1] > bee[x][y] + 1 && (a[x][y+1] != 'T' && a[x][y+1] != 'D')) {bee[x][y+1] = bee[x][y] + kk; p.push(mep(x, y+1));}
        if(y > 1 && bee[x][y-1] > bee[x][y] + 1 && (a[x][y-1] != 'T' && a[x][y-1] != 'D')) {bee[x][y-1] = bee[x][y] + kk; p.push(mep(x, y-1));}
    }
    // for(int i = 1; i <= n; i++) {
    //     for(int j = 1; j <= n; j++) {
    //         cout<<(bee[i][j] == INT_MAX ? -1 :bee[i][j])<<" ";
    //     }cout<<endl;
    // }
    int k = 0, mm = n * n;
    for(int i = mm/2; i >= 1; i /= 2) 
        while(i + k <= mm && can(i+k)) 
            k += i;
    cout<<(k == 0?-1:k);
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4736 KB Output is correct
2 Correct 8 ms 4736 KB Output is correct
3 Incorrect 7 ms 4736 KB Output isn't correct
4 Incorrect 7 ms 4736 KB Output isn't correct
5 Incorrect 8 ms 4760 KB Output isn't correct
6 Correct 7 ms 4736 KB Output is correct
7 Runtime error 369 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Correct 7 ms 4736 KB Output is correct
9 Correct 8 ms 4736 KB Output is correct
10 Incorrect 10 ms 4736 KB Output isn't correct
11 Incorrect 8 ms 4736 KB Output isn't correct
12 Incorrect 7 ms 4992 KB Output isn't correct
13 Incorrect 13 ms 5376 KB Output isn't correct
14 Correct 123 ms 10052 KB Output is correct
15 Incorrect 9 ms 4864 KB Output isn't correct
16 Incorrect 8 ms 4864 KB Output isn't correct
17 Incorrect 11 ms 4864 KB Output isn't correct
18 Incorrect 9 ms 4864 KB Output isn't correct
19 Incorrect 11 ms 4864 KB Output isn't correct
20 Incorrect 10 ms 4864 KB Output isn't correct
21 Incorrect 9 ms 4992 KB Output isn't correct
22 Incorrect 12 ms 4864 KB Output isn't correct
23 Incorrect 11 ms 4992 KB Output isn't correct
24 Incorrect 9 ms 4992 KB Output isn't correct
25 Incorrect 11 ms 4992 KB Output isn't correct
26 Incorrect 10 ms 4964 KB Output isn't correct
27 Incorrect 12 ms 5120 KB Output isn't correct
28 Incorrect 12 ms 4992 KB Output isn't correct
29 Incorrect 12 ms 5120 KB Output isn't correct
30 Incorrect 10 ms 5120 KB Output isn't correct
31 Incorrect 11 ms 5120 KB Output isn't correct
32 Incorrect 10 ms 5120 KB Output isn't correct
33 Incorrect 34 ms 6528 KB Output isn't correct
34 Incorrect 30 ms 6528 KB Output isn't correct
35 Runtime error 297 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Incorrect 24 ms 6784 KB Output isn't correct
37 Incorrect 21 ms 6648 KB Output isn't correct
38 Runtime error 293 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Incorrect 49 ms 7040 KB Output isn't correct
40 Incorrect 39 ms 7032 KB Output isn't correct
41 Runtime error 280 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Incorrect 34 ms 7160 KB Output isn't correct
43 Incorrect 32 ms 7164 KB Output isn't correct
44 Runtime error 304 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Incorrect 38 ms 7416 KB Output isn't correct
46 Incorrect 49 ms 7496 KB Output isn't correct
47 Runtime error 283 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 67 ms 7672 KB Output isn't correct
49 Incorrect 62 ms 7672 KB Output isn't correct
50 Runtime error 277 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Incorrect 78 ms 7928 KB Output isn't correct
52 Incorrect 68 ms 7928 KB Output isn't correct
53 Runtime error 300 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Incorrect 64 ms 8184 KB Output isn't correct
55 Incorrect 59 ms 8292 KB Output isn't correct
56 Runtime error 288 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Incorrect 111 ms 8568 KB Output isn't correct
58 Incorrect 91 ms 8440 KB Output isn't correct
59 Runtime error 284 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Incorrect 131 ms 8824 KB Output isn't correct
61 Incorrect 127 ms 8712 KB Output isn't correct
62 Runtime error 313 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Incorrect 281 ms 8824 KB Output isn't correct
64 Incorrect 281 ms 8836 KB Output isn't correct
65 Incorrect 248 ms 8696 KB Output isn't correct
66 Incorrect 291 ms 8696 KB Output isn't correct
67 Incorrect 285 ms 8824 KB Output isn't correct
68 Incorrect 306 ms 8824 KB Output isn't correct
69 Incorrect 302 ms 8820 KB Output isn't correct
70 Incorrect 279 ms 8696 KB Output isn't correct
71 Incorrect 283 ms 8824 KB Output isn't correct
72 Incorrect 246 ms 8760 KB Output isn't correct
73 Runtime error 512 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 471 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 499 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 485 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 497 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 479 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 440 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 473 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 451 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 440 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 399 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 408 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 411 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 383 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 368 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 361 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 348 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 435 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 347 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 401 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)