oj.uz

답안 #549424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
549424 2022-04-15T19:30:32 Z beaconmc Mecho (IOI09_mecho) PyPy 3
7 / 100
 1000 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])//s+1:
                    d.append([a,b,node[2]+1])
                    visited[a][b] = True
    return False
    
bfsinit()


for i in range(100, -1 ,-1):
    if test(i):
        print(i)
        break

Subtask #1
7.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 19200 KB Output isn't correct
2 Incorrect 58 ms 19332 KB Output isn't correct
3 Incorrect 63 ms 19300 KB Output isn't correct
4 Incorrect 48 ms 19176 KB Output isn't correct
5 Correct 47 ms 19220 KB Output is correct
6 Correct 51 ms 19204 KB Output is correct
7 Runtime error 258 ms 65536 KB Execution killed with signal 9
8 Incorrect 71 ms 19536 KB Output isn't correct
9 Correct 53 ms 19664 KB Output is correct
10 Correct 51 ms 19484 KB Output is correct
11 Correct 51 ms 19584 KB Output is correct
12 Incorrect 59 ms 20308 KB Output isn't correct
13 Incorrect 86 ms 21896 KB Output isn't correct
14 Incorrect 154 ms 24572 KB Output isn't correct
15 Incorrect 46 ms 18740 KB Output isn't correct
16 Correct 48 ms 19364 KB Output is correct
17 Incorrect 49 ms 19552 KB Output isn't correct
18 Incorrect 48 ms 19320 KB Output isn't correct
19 Incorrect 54 ms 19624 KB Output isn't correct
20 Incorrect 56 ms 19528 KB Output isn't correct
21 Incorrect 62 ms 20420 KB Output isn't correct
22 Incorrect 61 ms 20432 KB Output isn't correct
23 Incorrect 62 ms 20152 KB Output isn't correct
24 Incorrect 62 ms 20236 KB Output isn't correct
25 Incorrect 70 ms 20036 KB Output isn't correct
26 Incorrect 65 ms 19908 KB Output isn't correct
27 Incorrect 63 ms 20352 KB Output isn't correct
28 Incorrect 62 ms 20468 KB Output isn't correct
29 Incorrect 67 ms 20300 KB Output isn't correct
30 Incorrect 70 ms 20840 KB Output isn't correct
31 Incorrect 66 ms 20356 KB Output isn't correct
32 Incorrect 69 ms 20560 KB Output isn't correct
33 Incorrect 97 ms 29040 KB Output isn't correct
34 Incorrect 143 ms 30460 KB Output isn't correct
35 Execution timed out 1093 ms 38856 KB Time limit exceeded
36 Incorrect 116 ms 29992 KB Output isn't correct
37 Incorrect 134 ms 32380 KB Output isn't correct
38 Execution timed out 1080 ms 42044 KB Time limit exceeded
39 Incorrect 120 ms 33948 KB Output isn't correct
40 Incorrect 157 ms 36920 KB Output isn't correct
41 Execution timed out 1090 ms 50684 KB Time limit exceeded
42 Incorrect 149 ms 36540 KB Output isn't correct
43 Incorrect 162 ms 38352 KB Output isn't correct
44 Execution timed out 1085 ms 56428 KB Time limit exceeded
45 Incorrect 169 ms 42788 KB Output isn't correct
46 Incorrect 180 ms 42460 KB Output isn't correct
47 Execution timed out 1087 ms 60596 KB Time limit exceeded
48 Incorrect 172 ms 43780 KB Output isn't correct
49 Incorrect 193 ms 45884 KB Output isn't correct
50 Runtime error 708 ms 65536 KB Execution killed with signal 9
51 Incorrect 191 ms 51160 KB Output isn't correct
52 Incorrect 256 ms 53800 KB Output isn't correct
53 Runtime error 518 ms 65536 KB Execution killed with signal 9
54 Incorrect 227 ms 53496 KB Output isn't correct
55 Incorrect 230 ms 54784 KB Output isn't correct
56 Runtime error 526 ms 65536 KB Execution killed with signal 9
57 Incorrect 219 ms 58548 KB Output isn't correct
58 Incorrect 287 ms 62604 KB Output isn't correct
59 Runtime error 323 ms 65536 KB Execution killed with signal 9
60 Runtime error 301 ms 65536 KB Execution killed with signal 9
61 Runtime error 276 ms 65536 KB Execution killed with signal 9
62 Runtime error 306 ms 65536 KB Execution killed with signal 9
63 Runtime error 252 ms 65536 KB Execution killed with signal 9
64 Runtime error 319 ms 65536 KB Execution killed with signal 9
65 Runtime error 354 ms 65536 KB Execution killed with signal 9
66 Runtime error 249 ms 65536 KB Execution killed with signal 9
67 Runtime error 374 ms 65536 KB Execution killed with signal 9
68 Runtime error 226 ms 65536 KB Execution killed with signal 9
69 Runtime error 238 ms 65536 KB Execution killed with signal 9
70 Runtime error 216 ms 65536 KB Execution killed with signal 9
71 Runtime error 221 ms 65536 KB Execution killed with signal 9
72 Runtime error 226 ms 65536 KB Execution killed with signal 9
73 Runtime error 195 ms 65536 KB Execution killed with signal 9
74 Runtime error 212 ms 65536 KB Execution killed with signal 9
75 Runtime error 189 ms 65536 KB Execution killed with signal 9
76 Runtime error 191 ms 65536 KB Execution killed with signal 9
77 Runtime error 239 ms 65536 KB Execution killed with signal 9
78 Runtime error 244 ms 65536 KB Execution killed with signal 9
79 Runtime error 235 ms 65536 KB Execution killed with signal 9
80 Runtime error 254 ms 65536 KB Execution killed with signal 9
81 Runtime error 247 ms 65536 KB Execution killed with signal 9
82 Runtime error 240 ms 65536 KB Execution killed with signal 9
83 Runtime error 240 ms 65536 KB Execution killed with signal 9
84 Runtime error 276 ms 65536 KB Execution killed with signal 9
85 Runtime error 239 ms 65536 KB Execution killed with signal 9
86 Runtime error 241 ms 65536 KB Execution killed with signal 9
87 Runtime error 256 ms 65536 KB Execution killed with signal 9
88 Runtime error 247 ms 65536 KB Execution killed with signal 9
89 Runtime error 242 ms 65536 KB Execution killed with signal 9
90 Runtime error 242 ms 65536 KB Execution killed with signal 9
91 Runtime error 252 ms 65536 KB Execution killed with signal 9
92 Runtime error 266 ms 65536 KB Execution killed with signal 9