oj.uz

Submission #648216

# Submission time Handle Problem Language Result Execution time Memory
648216 2022-10-05T17:33:16 Z beaconmc Stranded Far From Home (BOI22_island) Python 3
0 / 100
 1000 ms 86344 KB 
import sys,io,os
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])
if n>1000:
    print("sus")
else:
    for i in ans:
        print(i,end="")

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2900 KB Output is correct
2 Correct 15 ms 2880 KB Output is correct
3 Correct 14 ms 2900 KB Output is correct
4 Incorrect 25 ms 3668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2892 KB Output is correct
2 Correct 15 ms 2996 KB Output is correct
3 Execution timed out 1100 ms 86344 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2900 KB Output is correct
2 Execution timed out 1089 ms 84584 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2900 KB Output is correct
2 Execution timed out 1099 ms 84688 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2900 KB Output is correct
2 Correct 15 ms 2880 KB Output is correct
3 Correct 14 ms 2900 KB Output is correct
4 Incorrect 25 ms 3668 KB Output isn't correct
5 Halted 0 ms 0 KB -