oj.uz

Submission #549427

# Submission time Handle Problem Language Result Execution time Memory
549427 2022-04-15T19:40:23 Z beaconmc Mecho (IOI09_mecho) PyPy 3
46 / 100
 769 ms 65536 KB 
from collections import *
n,s = map(int, input().split())
grid = [list(input()) for i in range(n)]

hives = []
start = []
end = []
for i in range(n):
    for j in range(n):
        if grid[i][j] == "M":
            start = [i,j]
        elif grid[i][j] == "D":
            end = [i,j]
        elif grid[i][j] == "H":
            hives.append([i,j])
            grid[i][j] = 0
def bfsinit():           
    d = deque()
    for i in hives:
        d.append(i+[0])
    while len(d):
        node = d.popleft()

        for a,b in [(0,1), (0,-1), (1, 0), (-1, 0)]:
            a += node[0]
            b += node[1]
            if 0<=a<n and 0<=b<n:
                if grid[a][b] == "G" or grid[a][b] == "M":
                    d.append([a,b,node[2]+1])
                    grid[a][b] = node[2]+1

def test(time):
    d = deque()
    visited = [[False for i in range(n)] for i in range(n)]
    d.append(start+[0])
    while len(d):
        node = d.popleft()
        if node[0] == end[0] and node[1]==end[1]:
            return True

        for a,b in [(0,1), (0,-1), (1, 0), (-1, 0)]:
            a += node[0]
            b += node[1]
            if 0<=a<n and 0<=b<n and not visited[a][b]:
                if grid[a][b]=="T":
                    continue
                if grid[a][b] == "D" or int(grid[a][b]) > time+(node[2]+1)//s:
                    d.append([a,b,node[2]+1])
                    visited[a][b] = True
    return False
    
bfsinit()


lo = -1
hi = n*n

while lo<hi:
    mid = lo+(hi-lo+1)//2
    if test(mid):
        lo = mid
    else:
        hi = mid-1
print(lo)

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18532 KB Output is correct
2 Correct 47 ms 18632 KB Output is correct
3 Correct 41 ms 18532 KB Output is correct
4 Correct 43 ms 18628 KB Output is correct
5 Correct 46 ms 18740 KB Output is correct
6 Correct 45 ms 18672 KB Output is correct
7 Runtime error 283 ms 65536 KB Execution killed with signal 9
8 Correct 46 ms 19136 KB Output is correct
9 Correct 47 ms 19192 KB Output is correct
10 Correct 51 ms 19196 KB Output is correct
11 Correct 49 ms 19132 KB Output is correct
12 Incorrect 65 ms 20268 KB Output isn't correct
13 Incorrect 99 ms 21456 KB Output isn't correct
14 Correct 89 ms 21508 KB Output is correct
15 Correct 49 ms 19300 KB Output is correct
16 Correct 48 ms 19216 KB Output is correct
17 Correct 59 ms 19588 KB Output is correct
18 Correct 60 ms 19880 KB Output is correct
19 Correct 72 ms 19720 KB Output is correct
20 Correct 79 ms 20096 KB Output is correct
21 Correct 63 ms 20520 KB Output is correct
22 Correct 82 ms 21200 KB Output is correct
23 Correct 69 ms 20164 KB Output is correct
24 Correct 81 ms 20880 KB Output is correct
25 Correct 78 ms 20220 KB Output is correct
26 Correct 99 ms 21160 KB Output is correct
27 Correct 66 ms 20376 KB Output is correct
28 Correct 81 ms 21764 KB Output is correct
29 Correct 66 ms 20148 KB Output is correct
30 Correct 83 ms 21632 KB Output is correct
31 Correct 67 ms 20288 KB Output is correct
32 Correct 81 ms 22156 KB Output is correct
33 Correct 166 ms 38556 KB Output is correct
34 Correct 179 ms 39336 KB Output is correct
35 Correct 392 ms 42740 KB Output is correct
36 Correct 191 ms 45320 KB Output is correct
37 Correct 216 ms 45576 KB Output is correct
38 Correct 585 ms 48672 KB Output is correct
39 Correct 189 ms 47728 KB Output is correct
40 Correct 268 ms 52404 KB Output is correct
41 Correct 734 ms 55800 KB Output is correct
42 Correct 222 ms 56228 KB Output is correct
43 Correct 344 ms 57520 KB Output is correct
44 Correct 769 ms 58944 KB Output is correct
45 Runtime error 247 ms 65536 KB Execution killed with signal 9
46 Runtime error 299 ms 65536 KB Execution killed with signal 9
47 Runtime error 329 ms 65536 KB Execution killed with signal 9
48 Runtime error 271 ms 65536 KB Execution killed with signal 9
49 Runtime error 276 ms 65536 KB Execution killed with signal 9
50 Runtime error 370 ms 65536 KB Execution killed with signal 9
51 Runtime error 258 ms 65536 KB Execution killed with signal 9
52 Runtime error 267 ms 65536 KB Execution killed with signal 9
53 Runtime error 455 ms 65536 KB Execution killed with signal 9
54 Runtime error 246 ms 65536 KB Execution killed with signal 9
55 Runtime error 253 ms 65536 KB Execution killed with signal 9
56 Runtime error 506 ms 65536 KB Execution killed with signal 9
57 Runtime error 266 ms 65536 KB Execution killed with signal 9
58 Runtime error 283 ms 65536 KB Execution killed with signal 9
59 Runtime error 354 ms 65536 KB Execution killed with signal 9
60 Runtime error 255 ms 65536 KB Execution killed with signal 9
61 Runtime error 306 ms 65536 KB Execution killed with signal 9
62 Runtime error 281 ms 65536 KB Execution killed with signal 9
63 Runtime error 270 ms 65536 KB Execution killed with signal 9
64 Runtime error 356 ms 65536 KB Execution killed with signal 9
65 Runtime error 351 ms 65536 KB Execution killed with signal 9
66 Runtime error 265 ms 65536 KB Execution killed with signal 9
67 Runtime error 339 ms 65536 KB Execution killed with signal 9
68 Runtime error 240 ms 65536 KB Execution killed with signal 9
69 Runtime error 212 ms 65536 KB Execution killed with signal 9
70 Runtime error 224 ms 65536 KB Execution killed with signal 9
71 Runtime error 220 ms 65536 KB Execution killed with signal 9
72 Runtime error 239 ms 65536 KB Execution killed with signal 9
73 Runtime error 196 ms 65536 KB Execution killed with signal 9
74 Runtime error 196 ms 65536 KB Execution killed with signal 9
75 Runtime error 248 ms 65536 KB Execution killed with signal 9
76 Runtime error 198 ms 65536 KB Execution killed with signal 9
77 Runtime error 235 ms 65536 KB Execution killed with signal 9
78 Runtime error 238 ms 65536 KB Execution killed with signal 9
79 Runtime error 248 ms 65536 KB Execution killed with signal 9
80 Runtime error 264 ms 65536 KB Execution killed with signal 9
81 Runtime error 244 ms 65536 KB Execution killed with signal 9
82 Runtime error 307 ms 65536 KB Execution killed with signal 9
83 Runtime error 248 ms 65536 KB Execution killed with signal 9
84 Runtime error 273 ms 65536 KB Execution killed with signal 9
85 Runtime error 254 ms 65536 KB Execution killed with signal 9
86 Runtime error 245 ms 65536 KB Execution killed with signal 9
87 Runtime error 251 ms 65536 KB Execution killed with signal 9
88 Runtime error 266 ms 65536 KB Execution killed with signal 9
89 Runtime error 256 ms 65536 KB Execution killed with signal 9
90 Runtime error 256 ms 65536 KB Execution killed with signal 9
91 Runtime error 269 ms 65536 KB Execution killed with signal 9
92 Runtime error 257 ms 65536 KB Execution killed with signal 9