Submission #626060

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
626060	2022-08-11T07:39:25 Z	54skyxenon	Mecho (IOI09_mecho)	Python 3	0 / 100	1000 ms	17120 KB

mecho

# https://oj.uz/problem/view/IOI09_mecho

from collections import deque
from math import ceil

n, s = map(int, input().split())

forest = []
for _ in range(n):
    forest.append(input())

start = None
end = None
hives = []

for i in range(n):
    for j in range(n):
        if forest[i][j] == 'M':
            start = (i, j)
        if forest[i][j] == 'D':
            end = (i, j)
        if forest[i][j] == 'H':
            hives.append((i, j))

dist_hive = [[float('inf')] * n for _ in range(n)]

hives_Q = deque()
for i, j in hives:
    dist_hive[i][j] = 0
    hives_Q.append((i, j, 0))

while hives_Q:
    r, c, depth = hives_Q.popleft()
    for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
        if 0 <= nr < n and 0 <= nc < n and forest[nr][nc] == 'G' and dist_hive[nr][nc] == float('inf'):
            hives_Q.append((nr, nc, depth + 1))
            dist_hive[nr][nc] = depth + 1

def bs(lo, hi):
    if not ok(lo):
        return -1
    
    global dist_hive

    def ok(midd):
        seen = [[False] * n for _ in range(n)]
        seen[start[0]][start[1]] = True

        mecho_Q = deque([(start[0], start[1], 0)])
        while mecho_Q:
            r, c, depth = mecho_Q.popleft()
            if (r, c) == end:
                return True

            for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
                if 0 <= nr < n and 0 <= nc < n and forest[nr][nc] in {'G', 'D'} and (midd + ((depth + 1) // s)) < dist_hive[nr][nc] and not seen[nr][nc]:
                    seen[nr][nc] = True
                    mecho_Q.append((nr, nc, depth + 1))

        return False

    while lo < hi:
        mid = lo + (hi - lo + 1) // 2

        if ok(mid):
            lo = mid
        else:
            hi = mid - 1

    return lo

print(bs(0, n ** 2))

Subtask #1
0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	17 ms	3284 KB	Execution failed because the return code was nonzero
2	Runtime error	16 ms	3380 KB	Execution failed because the return code was nonzero
3	Runtime error	21 ms	3320 KB	Execution failed because the return code was nonzero
4	Runtime error	16 ms	3412 KB	Execution failed because the return code was nonzero
5	Runtime error	19 ms	3320 KB	Execution failed because the return code was nonzero
6	Runtime error	18 ms	3404 KB	Execution failed because the return code was nonzero
7	Execution timed out	1089 ms	10604 KB	Time limit exceeded
8	Runtime error	17 ms	3356 KB	Execution failed because the return code was nonzero
9	Runtime error	17 ms	3412 KB	Execution failed because the return code was nonzero
10	Runtime error	17 ms	3412 KB	Execution failed because the return code was nonzero
11	Runtime error	16 ms	3404 KB	Execution failed because the return code was nonzero
12	Runtime error	24 ms	3364 KB	Execution failed because the return code was nonzero
13	Runtime error	29 ms	3432 KB	Execution failed because the return code was nonzero
14	Runtime error	30 ms	3448 KB	Execution failed because the return code was nonzero
15	Runtime error	17 ms	3412 KB	Execution failed because the return code was nonzero
16	Runtime error	17 ms	3412 KB	Execution failed because the return code was nonzero
17	Runtime error	22 ms	3412 KB	Execution failed because the return code was nonzero
18	Runtime error	17 ms	3396 KB	Execution failed because the return code was nonzero
19	Runtime error	19 ms	3412 KB	Execution failed because the return code was nonzero
20	Runtime error	23 ms	3412 KB	Execution failed because the return code was nonzero
21	Runtime error	23 ms	3412 KB	Execution failed because the return code was nonzero
22	Runtime error	19 ms	3332 KB	Execution failed because the return code was nonzero
23	Runtime error	21 ms	3432 KB	Execution failed because the return code was nonzero
24	Runtime error	21 ms	3412 KB	Execution failed because the return code was nonzero
25	Runtime error	23 ms	3464 KB	Execution failed because the return code was nonzero
26	Runtime error	24 ms	3472 KB	Execution failed because the return code was nonzero
27	Runtime error	24 ms	3420 KB	Execution failed because the return code was nonzero
28	Runtime error	26 ms	3448 KB	Execution failed because the return code was nonzero
29	Runtime error	25 ms	3440 KB	Execution failed because the return code was nonzero
30	Runtime error	27 ms	3448 KB	Execution failed because the return code was nonzero
31	Runtime error	27 ms	3384 KB	Execution failed because the return code was nonzero
32	Runtime error	26 ms	3436 KB	Execution failed because the return code was nonzero
33	Runtime error	252 ms	6408 KB	Execution failed because the return code was nonzero
34	Runtime error	259 ms	6520 KB	Execution failed because the return code was nonzero
35	Runtime error	377 ms	5672 KB	Execution failed because the return code was nonzero
36	Runtime error	336 ms	7304 KB	Execution failed because the return code was nonzero
37	Runtime error	328 ms	7268 KB	Execution failed because the return code was nonzero
38	Runtime error	526 ms	6752 KB	Execution failed because the return code was nonzero
39	Runtime error	408 ms	8344 KB	Execution failed because the return code was nonzero
40	Runtime error	436 ms	8396 KB	Execution failed because the return code was nonzero
41	Runtime error	690 ms	8108 KB	Execution failed because the return code was nonzero
42	Runtime error	520 ms	9616 KB	Execution failed because the return code was nonzero
43	Runtime error	517 ms	9584 KB	Execution failed because the return code was nonzero
44	Runtime error	865 ms	9552 KB	Execution failed because the return code was nonzero
45	Runtime error	624 ms	10844 KB	Execution failed because the return code was nonzero
46	Runtime error	613 ms	10836 KB	Execution failed because the return code was nonzero
47	Runtime error	958 ms	11248 KB	Execution failed because the return code was nonzero
48	Runtime error	799 ms	12324 KB	Execution failed because the return code was nonzero
49	Runtime error	799 ms	12252 KB	Execution failed because the return code was nonzero
50	Execution timed out	1079 ms	11608 KB	Time limit exceeded
51	Runtime error	965 ms	13848 KB	Execution failed because the return code was nonzero
52	Runtime error	937 ms	13792 KB	Execution failed because the return code was nonzero
53	Execution timed out	1077 ms	11640 KB	Time limit exceeded
54	Execution timed out	1075 ms	14624 KB	Time limit exceeded
55	Execution timed out	1039 ms	15512 KB	Time limit exceeded
56	Execution timed out	1098 ms	13388 KB	Time limit exceeded
57	Execution timed out	1086 ms	17032 KB	Time limit exceeded
58	Execution timed out	1093 ms	16176 KB	Time limit exceeded
59	Execution timed out	1092 ms	13924 KB	Time limit exceeded
60	Execution timed out	1090 ms	16572 KB	Time limit exceeded
61	Execution timed out	1086 ms	15908 KB	Time limit exceeded
62	Execution timed out	1095 ms	14612 KB	Time limit exceeded
63	Execution timed out	1097 ms	16012 KB	Time limit exceeded
64	Execution timed out	1085 ms	16988 KB	Time limit exceeded
65	Execution timed out	1093 ms	17120 KB	Time limit exceeded
66	Execution timed out	1097 ms	16724 KB	Time limit exceeded
67	Execution timed out	1099 ms	16304 KB	Time limit exceeded
68	Execution timed out	1092 ms	9544 KB	Time limit exceeded
69	Execution timed out	1088 ms	9652 KB	Time limit exceeded
70	Execution timed out	1090 ms	9552 KB	Time limit exceeded
71	Execution timed out	1098 ms	9628 KB	Time limit exceeded
72	Execution timed out	1094 ms	9504 KB	Time limit exceeded
73	Execution timed out	1086 ms	13520 KB	Time limit exceeded
74	Execution timed out	1092 ms	13236 KB	Time limit exceeded
75	Execution timed out	1047 ms	13288 KB	Time limit exceeded
76	Execution timed out	1082 ms	13252 KB	Time limit exceeded
77	Execution timed out	1091 ms	13208 KB	Time limit exceeded
78	Execution timed out	1093 ms	12252 KB	Time limit exceeded
79	Execution timed out	1081 ms	12496 KB	Time limit exceeded
80	Execution timed out	1050 ms	12164 KB	Time limit exceeded
81	Execution timed out	1088 ms	12280 KB	Time limit exceeded
82	Execution timed out	1096 ms	12268 KB	Time limit exceeded
83	Execution timed out	1091 ms	12072 KB	Time limit exceeded
84	Execution timed out	1084 ms	12068 KB	Time limit exceeded
85	Execution timed out	1065 ms	12128 KB	Time limit exceeded
86	Execution timed out	1053 ms	12100 KB	Time limit exceeded
87	Execution timed out	1094 ms	12104 KB	Time limit exceeded
88	Execution timed out	1087 ms	11544 KB	Time limit exceeded
89	Execution timed out	1082 ms	11404 KB	Time limit exceeded
90	Execution timed out	1078 ms	11448 KB	Time limit exceeded
91	Execution timed out	1065 ms	11468 KB	Time limit exceeded
92	Execution timed out	1094 ms	11464 KB	Time limit exceeded

Submission #626060

Compilation message

Subtask #1 0.0 / 100.0

Subtask #1
0.0 / 100.0