oj.uz

Submission #648202

# Submission time Handle Problem Language Result Execution time Memory
648202 2022-10-05T17:22:20 Z beaconmc Stranded Far From Home (BOI22_island) PyPy 3
10 / 100
 1000 ms 74716 KB 
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])
print("".join(map(str,ans)))

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 18132 KB Output is correct
2 Correct 38 ms 18144 KB Output is correct
3 Correct 34 ms 18252 KB Output is correct
4 Correct 126 ms 25204 KB Output is correct
5 Correct 130 ms 25128 KB Output is correct
6 Correct 132 ms 24416 KB Output is correct
7 Correct 126 ms 24728 KB Output is correct
8 Correct 114 ms 23856 KB Output is correct
9 Correct 115 ms 24872 KB Output is correct
10 Correct 133 ms 24576 KB Output is correct
11 Correct 146 ms 25104 KB Output is correct
12 Correct 139 ms 24948 KB Output is correct
13 Correct 125 ms 25476 KB Output is correct
14 Correct 139 ms 25028 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18132 KB Output is correct
2 Correct 37 ms 18204 KB Output is correct
3 Execution timed out 1098 ms 74656 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 18144 KB Output is correct
2 Execution timed out 1081 ms 74244 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18136 KB Output is correct
2 Execution timed out 1100 ms 74716 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 18132 KB Output is correct
2 Correct 38 ms 18144 KB Output is correct
3 Correct 34 ms 18252 KB Output is correct
4 Correct 126 ms 25204 KB Output is correct
5 Correct 130 ms 25128 KB Output is correct
6 Correct 132 ms 24416 KB Output is correct
7 Correct 126 ms 24728 KB Output is correct
8 Correct 114 ms 23856 KB Output is correct
9 Correct 115 ms 24872 KB Output is correct
10 Correct 133 ms 24576 KB Output is correct
11 Correct 146 ms 25104 KB Output is correct
12 Correct 139 ms 24948 KB Output is correct
13 Correct 125 ms 25476 KB Output is correct
14 Correct 139 ms 25028 KB Output is correct
15 Correct 37 ms 18132 KB Output is correct
16 Correct 37 ms 18204 KB Output is correct
17 Execution timed out 1098 ms 74656 KB Time limit exceeded
18 Halted 0 ms 0 KB -