Submission #1293338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293338		widici	Stranded Far From Home (BOI22_island)	Pypy 3	0 / 100	1102 ms	147648 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)]
    visited[origin] = True

    pq = []
    for next in adj[origin]:
        heapq.heappush(pq, (s[next], next))

    tot = s[origin]

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

        if visited[v]:
            continue

        if tot < ties:
            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