Submission #1293334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293334		widici	Stranded Far From Home (BOI22_island)	Pypy 3	0 / 100	153 ms	48732 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 = s[origin]

    while pq:
        _, v = heapq.heappop(pq)

        for next in adj[v]:
            if visited[next]:
                continue

            if s[next] <= tot:
                visited[next] = True
                tot += s[next]
                heapq.heappush(pq, (s[next], next))

    if not all(visited):
        res[origin] = "0"

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