Submission #103691

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
103691	2019-04-02T04:41:32 Z	Badral	Mecho (IOI09_mecho)	C++17	5 / 100	552 ms	66560 KB

mecho

#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')) {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')) {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')) {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')) {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

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	4736 KB	Output is correct
2	Incorrect	7 ms	4736 KB	Output isn't correct
3	Incorrect	9 ms	4736 KB	Output isn't correct
4	Incorrect	8 ms	4736 KB	Output isn't correct
5	Incorrect	9 ms	4736 KB	Output isn't correct
6	Incorrect	8 ms	4736 KB	Output isn't correct
7	Runtime error	346 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Correct	8 ms	4864 KB	Output is correct
9	Correct	8 ms	4864 KB	Output is correct
10	Incorrect	8 ms	4736 KB	Output isn't correct
11	Incorrect	9 ms	4736 KB	Output isn't correct
12	Incorrect	8 ms	4992 KB	Output isn't correct
13	Incorrect	14 ms	5376 KB	Output isn't correct
14	Correct	138 ms	9972 KB	Output is correct
15	Incorrect	9 ms	4864 KB	Output isn't correct
16	Incorrect	9 ms	4864 KB	Output isn't correct
17	Incorrect	10 ms	4864 KB	Output isn't correct
18	Incorrect	9 ms	4864 KB	Output isn't correct
19	Incorrect	10 ms	4864 KB	Output isn't correct
20	Incorrect	9 ms	4864 KB	Output isn't correct
21	Incorrect	9 ms	4992 KB	Output isn't correct
22	Incorrect	10 ms	4864 KB	Output isn't correct
23	Incorrect	9 ms	4992 KB	Output isn't correct
24	Incorrect	10 ms	4992 KB	Output isn't correct
25	Incorrect	12 ms	4992 KB	Output isn't correct
26	Incorrect	11 ms	4992 KB	Output isn't correct
27	Incorrect	10 ms	5120 KB	Output isn't correct
28	Incorrect	12 ms	5120 KB	Output isn't correct
29	Incorrect	12 ms	5092 KB	Output isn't correct
30	Incorrect	11 ms	5120 KB	Output isn't correct
31	Incorrect	11 ms	5120 KB	Output isn't correct
32	Incorrect	12 ms	5120 KB	Output isn't correct
33	Incorrect	38 ms	6528 KB	Output isn't correct
34	Incorrect	31 ms	6400 KB	Output isn't correct
35	Runtime error	291 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
36	Incorrect	24 ms	6776 KB	Output isn't correct
37	Incorrect	21 ms	6652 KB	Output isn't correct
38	Runtime error	283 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Incorrect	45 ms	7032 KB	Output isn't correct
40	Incorrect	36 ms	6912 KB	Output isn't correct
41	Runtime error	257 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
42	Incorrect	30 ms	7296 KB	Output isn't correct
43	Incorrect	35 ms	7160 KB	Output isn't correct
44	Runtime error	280 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
45	Incorrect	45 ms	7416 KB	Output isn't correct
46	Incorrect	40 ms	7544 KB	Output isn't correct
47	Runtime error	288 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
48	Incorrect	74 ms	7800 KB	Output isn't correct
49	Incorrect	69 ms	7800 KB	Output isn't correct
50	Runtime error	295 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Incorrect	83 ms	7936 KB	Output isn't correct
52	Incorrect	81 ms	8056 KB	Output isn't correct
53	Runtime error	285 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
54	Incorrect	54 ms	8188 KB	Output isn't correct
55	Incorrect	55 ms	8184 KB	Output isn't correct
56	Runtime error	301 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
57	Incorrect	105 ms	8440 KB	Output isn't correct
58	Incorrect	71 ms	8440 KB	Output isn't correct
59	Runtime error	289 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
60	Incorrect	112 ms	8696 KB	Output isn't correct
61	Incorrect	106 ms	8696 KB	Output isn't correct
62	Runtime error	327 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
63	Incorrect	325 ms	8860 KB	Output isn't correct
64	Incorrect	284 ms	8696 KB	Output isn't correct
65	Incorrect	259 ms	8696 KB	Output isn't correct
66	Incorrect	271 ms	8796 KB	Output isn't correct
67	Incorrect	302 ms	8824 KB	Output isn't correct
68	Incorrect	259 ms	8824 KB	Output isn't correct
69	Incorrect	268 ms	8824 KB	Output isn't correct
70	Incorrect	268 ms	8696 KB	Output isn't correct
71	Incorrect	254 ms	8696 KB	Output isn't correct
72	Incorrect	233 ms	8700 KB	Output isn't correct
73	Runtime error	552 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
74	Runtime error	533 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
75	Runtime error	530 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
76	Runtime error	469 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
77	Runtime error	531 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
78	Runtime error	444 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
79	Runtime error	479 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
80	Runtime error	507 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
81	Runtime error	473 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
82	Runtime error	506 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
83	Runtime error	379 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
84	Runtime error	420 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
85	Runtime error	371 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
86	Runtime error	385 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
87	Runtime error	409 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
88	Runtime error	385 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
89	Runtime error	326 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
90	Runtime error	376 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
91	Runtime error	359 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
92	Runtime error	388 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)