oj.uz

Submission #626033

# Submission time Handle Problem Language Result Execution time Memory
626033 2022-08-11T06:51:21 Z 54skyxenon Mecho (IOI09_mecho) Python 3
19 / 100
 1000 ms 25668 KB 
# 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))

def bs(lo, hi):
    def ok(mid):
        dist_hive = [[float('inf')] * n for _ in range(n)]
        dist_mecho = [[float('inf')] * n for _ in range(n)]
        dist_mecho[start[0]][start[1]] = mid

        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

        mecho_Q = deque([(start[0], start[1], 0)])
        while mecho_Q:
            r, c, depth = mecho_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_mecho[nr][nc] == float('inf'):
                    mecho_Q.append((nr, nc, depth + 1))
                    dist_mecho[nr][nc] = mid + ceil((depth + 1) / s)

        # print('at mid =', mid)
        # print('dist_hive:')
        # print(*dist_hive, sep='\n')
        # print('dist_mecho:')
        # print(*dist_mecho, sep='\n')

        r, c = end
        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_mecho[nr][nc] < dist_hive[nr][nc]:
                # print('mid =', mid, 'is good!')
                return True

        # print('mid =', mid, 'is bad!')
        return False

    if lo > hi:
        return -1

    mid = (lo + hi) // 2

    if not ok(mid):
        return bs(lo, mid - 1)
    elif mid < hi and ok(mid + 1):
        return bs(mid + 1, hi)
    else:
        return mid

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

Subtask #1
19.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3380 KB Output is correct
2 Correct 19 ms 3364 KB Output is correct
3 Correct 18 ms 3404 KB Output is correct
4 Correct 17 ms 3412 KB Output is correct
5 Incorrect 18 ms 3324 KB Output isn't correct
6 Incorrect 19 ms 3428 KB Output isn't correct
7 Execution timed out 1077 ms 16424 KB Time limit exceeded
8 Correct 26 ms 3388 KB Output is correct
9 Incorrect 29 ms 3392 KB Output isn't correct
10 Incorrect 28 ms 3348 KB Output isn't correct
11 Incorrect 31 ms 3420 KB Output isn't correct
12 Incorrect 109 ms 3508 KB Output isn't correct
13 Incorrect 164 ms 3412 KB Output isn't correct
14 Correct 212 ms 3568 KB Output is correct
15 Correct 33 ms 3404 KB Output is correct
16 Incorrect 28 ms 3420 KB Output isn't correct
17 Correct 37 ms 3364 KB Output is correct
18 Incorrect 34 ms 3344 KB Output isn't correct
19 Correct 52 ms 3436 KB Output is correct
20 Incorrect 61 ms 3404 KB Output isn't correct
21 Correct 92 ms 3532 KB Output is correct
22 Incorrect 74 ms 3412 KB Output isn't correct
23 Correct 113 ms 3504 KB Output is correct
24 Incorrect 113 ms 3520 KB Output isn't correct
25 Correct 203 ms 3556 KB Output is correct
26 Incorrect 171 ms 3552 KB Output isn't correct
27 Correct 222 ms 3576 KB Output is correct
28 Incorrect 234 ms 3564 KB Output isn't correct
29 Correct 241 ms 3604 KB Output is correct
30 Incorrect 262 ms 3604 KB Output isn't correct
31 Correct 275 ms 3656 KB Output is correct
32 Incorrect 280 ms 3620 KB Output isn't correct
33 Execution timed out 1077 ms 9564 KB Time limit exceeded
34 Execution timed out 1078 ms 9644 KB Time limit exceeded
35 Execution timed out 1079 ms 9724 KB Time limit exceeded
36 Execution timed out 1069 ms 11412 KB Time limit exceeded
37 Execution timed out 1063 ms 11520 KB Time limit exceeded
38 Execution timed out 1081 ms 11956 KB Time limit exceeded
39 Execution timed out 1087 ms 13520 KB Time limit exceeded
40 Execution timed out 1079 ms 13612 KB Time limit exceeded
41 Execution timed out 1084 ms 14764 KB Time limit exceeded
42 Execution timed out 1081 ms 15828 KB Time limit exceeded
43 Execution timed out 1085 ms 15796 KB Time limit exceeded
44 Execution timed out 1053 ms 16672 KB Time limit exceeded
45 Execution timed out 1062 ms 18464 KB Time limit exceeded
46 Execution timed out 1075 ms 18560 KB Time limit exceeded
47 Execution timed out 1084 ms 16848 KB Time limit exceeded
48 Execution timed out 1074 ms 20356 KB Time limit exceeded
49 Execution timed out 1084 ms 20128 KB Time limit exceeded
50 Execution timed out 1095 ms 18008 KB Time limit exceeded
51 Execution timed out 1063 ms 20376 KB Time limit exceeded
52 Execution timed out 1068 ms 20204 KB Time limit exceeded
53 Execution timed out 1061 ms 18000 KB Time limit exceeded
54 Execution timed out 1076 ms 22480 KB Time limit exceeded
55 Execution timed out 1087 ms 22236 KB Time limit exceeded
56 Execution timed out 1087 ms 19196 KB Time limit exceeded
57 Execution timed out 1070 ms 22408 KB Time limit exceeded
58 Execution timed out 1078 ms 23636 KB Time limit exceeded
59 Execution timed out 1046 ms 20008 KB Time limit exceeded
60 Execution timed out 1078 ms 24292 KB Time limit exceeded
61 Execution timed out 1079 ms 25668 KB Time limit exceeded
62 Execution timed out 1088 ms 22504 KB Time limit exceeded
63 Execution timed out 1085 ms 23888 KB Time limit exceeded
64 Execution timed out 1074 ms 24824 KB Time limit exceeded
65 Execution timed out 1089 ms 24740 KB Time limit exceeded
66 Execution timed out 1094 ms 24936 KB Time limit exceeded
67 Execution timed out 1092 ms 25264 KB Time limit exceeded
68 Execution timed out 1057 ms 15300 KB Time limit exceeded
69 Execution timed out 1036 ms 15448 KB Time limit exceeded
70 Execution timed out 1080 ms 15344 KB Time limit exceeded
71 Execution timed out 1077 ms 15236 KB Time limit exceeded
72 Execution timed out 1057 ms 15300 KB Time limit exceeded
73 Execution timed out 1085 ms 18912 KB Time limit exceeded
74 Execution timed out 1067 ms 18924 KB Time limit exceeded
75 Execution timed out 1081 ms 18948 KB Time limit exceeded
76 Execution timed out 1081 ms 18908 KB Time limit exceeded
77 Execution timed out 1071 ms 18984 KB Time limit exceeded
78 Execution timed out 1089 ms 18020 KB Time limit exceeded
79 Execution timed out 1078 ms 18104 KB Time limit exceeded
80 Execution timed out 1086 ms 17936 KB Time limit exceeded
81 Execution timed out 1075 ms 18132 KB Time limit exceeded
82 Execution timed out 1044 ms 18012 KB Time limit exceeded
83 Execution timed out 1085 ms 17736 KB Time limit exceeded
84 Execution timed out 1081 ms 17920 KB Time limit exceeded
85 Execution timed out 1089 ms 17760 KB Time limit exceeded
86 Execution timed out 1080 ms 17828 KB Time limit exceeded
87 Execution timed out 1088 ms 17748 KB Time limit exceeded
88 Execution timed out 1075 ms 17112 KB Time limit exceeded
89 Execution timed out 1089 ms 17128 KB Time limit exceeded
90 Execution timed out 1082 ms 17284 KB Time limit exceeded
91 Execution timed out 1082 ms 17288 KB Time limit exceeded
92 Execution timed out 1092 ms 17108 KB Time limit exceeded