| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 648211 | beaconmc | Stranded Far From Home (BOI22_island) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
'''
sys.stdin = open("/Users/beaconmc/Downloads/in.txt", "r")
sys.stdout = open("sus.txt","w")
'''
def find(a):
while cc[a] != a:
cc[a] = cc[cc[a]]
a = cc[a]
return a
def union(a, b):
aa = find(a)
bb = find(b)
if aa==bb: return
if siz[aa] < sizes[b]:
for i in stuff[aa]:
ans[i] = 0
stuff[aa] = []
if siz[bb] < sizes[a]:
for i in stuff[bb]:
ans[i] = 0
stuff[bb] = []
if len(stuff[aa]) > len(stuff[bb]):
stuff[aa],stuff[bb] = stuff[bb], stuff[aa]
for i in stuff[aa]:
stuff[bb].append(i)
siz[bb] += siz[aa]
cc[aa] = bb
n,m = map(int, input().split())
cc = [i for i in range(n)]
sizes = list(map(int, input().split()))
siz = list(sizes)
stuff = [[i]for i in range(n)]
ans = [1 for i in range(n)]
edges = []
for i in range(m):
a,b = map(int, input().split())
a-=1;b-=1
edges.append([max(sizes[a],sizes[b]),min(sizes[a],sizes[b]), a,b])
edges.sort()
for i in edges:
union(i[2],i[3])
for i in ans:
print(i,end="")