oj.uz

Submission #648213

# Submission time Handle Problem Language Result Execution time Memory
648213 2022-10-05T17:32:14 Z beaconmc Stranded Far From Home (BOI22_island) PyPy 3
10 / 100
 1000 ms 80948 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])
for i in ans:
    print(i,end="")

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 18164 KB Output is correct
2 Correct 39 ms 18132 KB Output is correct
3 Correct 45 ms 18180 KB Output is correct
4 Correct 108 ms 24728 KB Output is correct
5 Correct 118 ms 25100 KB Output is correct
6 Correct 111 ms 24072 KB Output is correct
7 Correct 115 ms 24216 KB Output is correct
8 Correct 107 ms 23604 KB Output is correct
9 Correct 115 ms 24616 KB Output is correct
10 Correct 114 ms 24460 KB Output is correct
11 Correct 119 ms 24868 KB Output is correct
12 Correct 104 ms 25088 KB Output is correct
13 Correct 102 ms 25188 KB Output is correct
14 Correct 113 ms 24584 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18216 KB Output is correct
2 Correct 36 ms 18216 KB Output is correct
3 Execution timed out 1098 ms 80596 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 18164 KB Output is correct
2 Execution timed out 1091 ms 80948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18220 KB Output is correct
2 Execution timed out 1085 ms 80508 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 18164 KB Output is correct
2 Correct 39 ms 18132 KB Output is correct
3 Correct 45 ms 18180 KB Output is correct
4 Correct 108 ms 24728 KB Output is correct
5 Correct 118 ms 25100 KB Output is correct
6 Correct 111 ms 24072 KB Output is correct
7 Correct 115 ms 24216 KB Output is correct
8 Correct 107 ms 23604 KB Output is correct
9 Correct 115 ms 24616 KB Output is correct
10 Correct 114 ms 24460 KB Output is correct
11 Correct 119 ms 24868 KB Output is correct
12 Correct 104 ms 25088 KB Output is correct
13 Correct 102 ms 25188 KB Output is correct
14 Correct 113 ms 24584 KB Output is correct
15 Correct 36 ms 18216 KB Output is correct
16 Correct 36 ms 18216 KB Output is correct
17 Execution timed out 1098 ms 80596 KB Time limit exceeded
18 Halted 0 ms 0 KB -