oj.uz

답안 #549425

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
549425 2022-04-15T19:38:05 Z beaconmc Mecho (IOI09_mecho) PyPy 3
38 / 100
 739 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 = 0
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
38.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 18564 KB Output is correct
2 Correct 42 ms 18608 KB Output is correct
3 Correct 42 ms 18584 KB Output is correct
4 Correct 43 ms 18720 KB Output is correct
5 Correct 42 ms 18700 KB Output is correct
6 Correct 45 ms 18636 KB Output is correct
7 Runtime error 260 ms 65536 KB Execution killed with signal 9
8 Incorrect 45 ms 19144 KB Output isn't correct
9 Correct 45 ms 19172 KB Output is correct
10 Correct 46 ms 19112 KB Output is correct
11 Correct 50 ms 19172 KB Output is correct
12 Incorrect 60 ms 20188 KB Output isn't correct
13 Incorrect 77 ms 21536 KB Output isn't correct
14 Incorrect 77 ms 21688 KB Output isn't correct
15 Correct 46 ms 19272 KB Output is correct
16 Correct 53 ms 19236 KB Output is correct
17 Correct 52 ms 19604 KB Output is correct
18 Correct 55 ms 19812 KB Output is correct
19 Correct 56 ms 19752 KB Output is correct
20 Correct 61 ms 20196 KB Output is correct
21 Correct 62 ms 20520 KB Output is correct
22 Correct 71 ms 21124 KB Output is correct
23 Correct 66 ms 20172 KB Output is correct
24 Correct 78 ms 20928 KB Output is correct
25 Correct 67 ms 20220 KB Output is correct
26 Correct 82 ms 21092 KB Output is correct
27 Correct 66 ms 20488 KB Output is correct
28 Correct 86 ms 21776 KB Output is correct
29 Correct 66 ms 20180 KB Output is correct
30 Correct 83 ms 21680 KB Output is correct
31 Correct 65 ms 20204 KB Output is correct
32 Correct 80 ms 22204 KB Output is correct
33 Correct 138 ms 38460 KB Output is correct
34 Correct 177 ms 38000 KB Output is correct
35 Correct 452 ms 42480 KB Output is correct
36 Correct 158 ms 44968 KB Output is correct
37 Correct 204 ms 45268 KB Output is correct
38 Correct 436 ms 48576 KB Output is correct
39 Correct 172 ms 47448 KB Output is correct
40 Correct 222 ms 52268 KB Output is correct
41 Correct 584 ms 55720 KB Output is correct
42 Correct 230 ms 55896 KB Output is correct
43 Correct 245 ms 57356 KB Output is correct
44 Correct 739 ms 58556 KB Output is correct
45 Runtime error 255 ms 65536 KB Execution killed with signal 9
46 Runtime error 267 ms 65536 KB Execution killed with signal 9
47 Runtime error 318 ms 65536 KB Execution killed with signal 9
48 Runtime error 223 ms 65536 KB Execution killed with signal 9
49 Runtime error 275 ms 65536 KB Execution killed with signal 9
50 Runtime error 357 ms 65536 KB Execution killed with signal 9
51 Runtime error 227 ms 65536 KB Execution killed with signal 9
52 Runtime error 267 ms 65536 KB Execution killed with signal 9
53 Runtime error 427 ms 65536 KB Execution killed with signal 9
54 Runtime error 271 ms 65536 KB Execution killed with signal 9
55 Runtime error 299 ms 65536 KB Execution killed with signal 9
56 Runtime error 545 ms 65536 KB Execution killed with signal 9
57 Runtime error 277 ms 65536 KB Execution killed with signal 9
58 Runtime error 277 ms 65536 KB Execution killed with signal 9
59 Runtime error 346 ms 65536 KB Execution killed with signal 9
60 Runtime error 282 ms 65536 KB Execution killed with signal 9
61 Runtime error 290 ms 65536 KB Execution killed with signal 9
62 Runtime error 318 ms 65536 KB Execution killed with signal 9
63 Runtime error 296 ms 65536 KB Execution killed with signal 9
64 Runtime error 378 ms 65536 KB Execution killed with signal 9
65 Runtime error 343 ms 65536 KB Execution killed with signal 9
66 Runtime error 265 ms 65536 KB Execution killed with signal 9
67 Runtime error 350 ms 65536 KB Execution killed with signal 9
68 Runtime error 232 ms 65536 KB Execution killed with signal 9
69 Runtime error 222 ms 65536 KB Execution killed with signal 9
70 Runtime error 228 ms 65536 KB Execution killed with signal 9
71 Runtime error 234 ms 65536 KB Execution killed with signal 9
72 Runtime error 228 ms 65536 KB Execution killed with signal 9
73 Runtime error 206 ms 65536 KB Execution killed with signal 9
74 Runtime error 211 ms 65536 KB Execution killed with signal 9
75 Runtime error 205 ms 65536 KB Execution killed with signal 9
76 Runtime error 214 ms 65536 KB Execution killed with signal 9
77 Runtime error 203 ms 65536 KB Execution killed with signal 9
78 Runtime error 268 ms 65536 KB Execution killed with signal 9
79 Runtime error 280 ms 65536 KB Execution killed with signal 9
80 Runtime error 256 ms 65536 KB Execution killed with signal 9
81 Runtime error 276 ms 65536 KB Execution killed with signal 9
82 Runtime error 269 ms 65536 KB Execution killed with signal 9
83 Runtime error 261 ms 65536 KB Execution killed with signal 9
84 Runtime error 252 ms 65536 KB Execution killed with signal 9
85 Runtime error 272 ms 65536 KB Execution killed with signal 9
86 Runtime error 259 ms 65536 KB Execution killed with signal 9
87 Runtime error 263 ms 65536 KB Execution killed with signal 9
88 Runtime error 267 ms 65536 KB Execution killed with signal 9
89 Runtime error 264 ms 65536 KB Execution killed with signal 9
90 Runtime error 262 ms 65536 KB Execution killed with signal 9
91 Runtime error 250 ms 65536 KB Execution killed with signal 9
92 Runtime error 249 ms 65536 KB Execution killed with signal 9