Submission #1293327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293327		widici	Stranded Far From Home (BOI22_island)	Pypy 3	0 / 100	1105 ms	147808 KiB

island

"""
Subtask 1
    N <= 2e3
    M <= 2e3
    O(N * (N + M) * log N) = 8.773e7
"""

import heapq

n, m = map(int, input().split())
s = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for a, b in [map(int, input().split()) for _ in range(m)]:
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

res = ["1" for _ in range(n)]

for origin in range(n):
    visited = [False for _ in range(n)]
    pq = [(s[origin], origin)]
    heapq.heapify(pq)
    tot = 0

    while pq:
        ties, v = heapq.heappop(pq)
        if tot < ties and not v == origin:
            res[origin] = "0"
            break
        tot += ties
        visited[v] = True

        for next in adj[v]:
            if visited[next]:
                continue
            heapq.heappush(pq, (s[next], next))

print("".join(res))

Compilation message (stdout)

Compiling 'island.py'...

=======
  adding: __main__.pyc (deflated 44%)

=======

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35