oj.uz

Submission #103694

# Submission time Handle Problem Language Result Execution time Memory
103694 2019-04-02T04:46:29 Z Badral Mecho (IOI09_mecho) C++17
10 / 100
 1000 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));}
    }
    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*n; i++) {
        if(can(i))
        return cout<<i, 0;
    }
    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 7 ms 4736 KB Output is correct
2 Correct 6 ms 4736 KB Output is correct
3 Incorrect 6 ms 4736 KB Output isn't correct
4 Incorrect 6 ms 4736 KB Output isn't correct
5 Incorrect 6 ms 4736 KB Output isn't correct
6 Correct 6 ms 4736 KB Output is correct
7 Runtime error 339 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Correct 54 ms 4864 KB Output is correct
9 Incorrect 6 ms 4736 KB Output isn't correct
10 Incorrect 7 ms 4864 KB Output isn't correct
11 Incorrect 6 ms 4736 KB Output isn't correct
12 Incorrect 7 ms 4992 KB Output isn't correct
13 Incorrect 12 ms 5376 KB Output isn't correct
14 Correct 904 ms 10060 KB Output is correct
15 Incorrect 6 ms 4864 KB Output isn't correct
16 Incorrect 6 ms 4864 KB Output isn't correct
17 Incorrect 6 ms 4864 KB Output isn't correct
18 Incorrect 6 ms 4864 KB Output isn't correct
19 Incorrect 6 ms 4864 KB Output isn't correct
20 Incorrect 5 ms 4864 KB Output isn't correct
21 Incorrect 6 ms 4864 KB Output isn't correct
22 Incorrect 6 ms 4864 KB Output isn't correct
23 Incorrect 6 ms 4992 KB Output isn't correct
24 Incorrect 6 ms 4992 KB Output isn't correct
25 Incorrect 6 ms 4992 KB Output isn't correct
26 Incorrect 6 ms 4992 KB Output isn't correct
27 Incorrect 6 ms 5120 KB Output isn't correct
28 Incorrect 6 ms 5120 KB Output isn't correct
29 Incorrect 6 ms 5120 KB Output isn't correct
30 Incorrect 6 ms 4992 KB Output isn't correct
31 Incorrect 8 ms 5120 KB Output isn't correct
32 Incorrect 7 ms 5120 KB Output isn't correct
33 Incorrect 16 ms 6400 KB Output isn't correct
34 Incorrect 17 ms 6528 KB Output isn't correct
35 Runtime error 266 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Incorrect 20 ms 6656 KB Output isn't correct
37 Incorrect 22 ms 6656 KB Output isn't correct
38 Runtime error 273 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Incorrect 14 ms 7040 KB Output isn't correct
40 Incorrect 22 ms 6908 KB Output isn't correct
41 Runtime error 301 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Incorrect 25 ms 7168 KB Output isn't correct
43 Incorrect 27 ms 7288 KB Output isn't correct
44 Runtime error 293 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Incorrect 30 ms 7416 KB Output isn't correct
46 Incorrect 34 ms 7416 KB Output isn't correct
47 Runtime error 289 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 35 ms 7800 KB Output isn't correct
49 Incorrect 37 ms 7672 KB Output isn't correct
50 Runtime error 300 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Incorrect 54 ms 7928 KB Output isn't correct
52 Incorrect 51 ms 8056 KB Output isn't correct
53 Runtime error 295 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Incorrect 40 ms 8184 KB Output isn't correct
55 Incorrect 52 ms 8312 KB Output isn't correct
56 Runtime error 291 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Incorrect 45 ms 8440 KB Output isn't correct
58 Incorrect 59 ms 8440 KB Output isn't correct
59 Runtime error 273 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Incorrect 70 ms 8696 KB Output isn't correct
61 Incorrect 70 ms 8824 KB Output isn't correct
62 Runtime error 289 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Execution timed out 1073 ms 8696 KB Time limit exceeded
64 Incorrect 85 ms 8696 KB Output isn't correct
65 Incorrect 77 ms 8824 KB Output isn't correct
66 Incorrect 79 ms 8696 KB Output isn't correct
67 Execution timed out 1077 ms 8696 KB Time limit exceeded
68 Incorrect 65 ms 8696 KB Output isn't correct
69 Incorrect 66 ms 8696 KB Output isn't correct
70 Incorrect 65 ms 8696 KB Output isn't correct
71 Incorrect 63 ms 8696 KB Output isn't correct
72 Incorrect 68 ms 8696 KB Output isn't correct
73 Runtime error 468 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 494 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 497 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 507 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 504 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 447 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 458 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 451 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 497 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 449 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 432 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 453 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 419 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 380 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 369 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 355 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 359 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 359 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 356 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 353 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)