Submission #49208917

Source Code Expand

from heapq import *

class Union:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.size = [1] * n
    
    def find(self, i):
        if self.p[i] != i:
            self.p[i] = self.find(self.p[i])
        return self.p[i]
    
    def link(self, i, j):
        i, j = self.find(i), self.find(j)
        if self.size[i] < self.size[j]:
            i, j = j, i
        self.p[j] = i
        self.size[i] += self.size[j]

n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
A = [[] for _ in range(n)]
Aij = []
U = Union(n)
for _ in range(m):
    u, v = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    if a[u] == a[v]:
        U.link(u, v)
    else:
        Aij.append((u, v))
for u, v in Aij:
    u = U.find(u)
    v = U.find(v)
    if a[u] < a[v]:
        A[u].append(v)
    elif a[v] < a[u]:
        A[v].append(u)
ds = [0] * n
cur = [(0, -1, U.find(0))] # value, -d, node
ds[U.find(0)] = 1
while cur:
    _, d, node = heappop(cur)
    d = -d
    if d != ds[node]:
        continue
    for child in A[node]:
        if d + 1 <= ds[child]:
            continue
        ds[child] = d + 1
        heappush(cur, (a[child], -(d + 1), child))
    # print(cur)
# print(A, ds)
print(ds[U.find(n - 1)])

Submission Info

Submission Time
Task E - Non-Decreasing Colorful Path
User shinever
Language Python (PyPy 3.10-v7.3.12)
Score 525
Code Size 1316 Byte
Status AC
Exec Time 779 ms
Memory 140568 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 525 / 525
Status
AC × 3
AC × 95
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt, test_58.txt, test_59.txt, test_60.txt, test_61.txt, test_62.txt, test_63.txt, test_64.txt, test_65.txt, test_66.txt, test_67.txt, test_68.txt, test_69.txt, test_70.txt, test_71.txt, test_72.txt, test_73.txt, test_74.txt, test_75.txt, test_76.txt, test_77.txt, test_78.txt, test_79.txt, test_80.txt, test_81.txt, test_82.txt, test_83.txt, test_84.txt, test_85.txt, test_86.txt, test_87.txt, test_88.txt, test_89.txt, test_90.txt
Case Name Status Exec Time Memory
hand_01.txt AC 59 ms 76368 KiB
hand_02.txt AC 58 ms 76544 KiB
sample_01.txt AC 59 ms 76576 KiB
sample_02.txt AC 58 ms 76316 KiB
sample_03.txt AC 59 ms 76444 KiB
test_01.txt AC 61 ms 76308 KiB
test_02.txt AC 285 ms 126604 KiB
test_03.txt AC 294 ms 112060 KiB
test_04.txt AC 215 ms 112244 KiB
test_05.txt AC 659 ms 85696 KiB
test_06.txt AC 187 ms 103284 KiB
test_07.txt AC 181 ms 99092 KiB
test_08.txt AC 201 ms 100804 KiB
test_09.txt AC 188 ms 96952 KiB
test_10.txt AC 244 ms 103836 KiB
test_11.txt AC 125 ms 87444 KiB
test_12.txt AC 205 ms 83320 KiB
test_13.txt AC 152 ms 94172 KiB
test_14.txt AC 165 ms 93632 KiB
test_15.txt AC 104 ms 84256 KiB
test_16.txt AC 171 ms 88036 KiB
test_17.txt AC 200 ms 93300 KiB
test_18.txt AC 448 ms 84668 KiB
test_19.txt AC 180 ms 101652 KiB
test_20.txt AC 103 ms 84588 KiB
test_21.txt AC 155 ms 87028 KiB
test_22.txt AC 181 ms 91600 KiB
test_23.txt AC 365 ms 106480 KiB
test_24.txt AC 536 ms 84888 KiB
test_25.txt AC 94 ms 83468 KiB
test_26.txt AC 131 ms 88160 KiB
test_27.txt AC 159 ms 89032 KiB
test_28.txt AC 186 ms 94384 KiB
test_29.txt AC 175 ms 95844 KiB
test_30.txt AC 116 ms 83044 KiB
test_31.txt AC 120 ms 86600 KiB
test_32.txt AC 139 ms 89408 KiB
test_33.txt AC 159 ms 94364 KiB
test_34.txt AC 177 ms 95672 KiB
test_35.txt AC 87 ms 83488 KiB
test_36.txt AC 173 ms 83484 KiB
test_37.txt AC 135 ms 89264 KiB
test_38.txt AC 155 ms 92764 KiB
test_39.txt AC 192 ms 98896 KiB
test_40.txt AC 111 ms 84528 KiB
test_41.txt AC 583 ms 117976 KiB
test_42.txt AC 561 ms 114660 KiB
test_43.txt AC 678 ms 123368 KiB
test_44.txt AC 675 ms 122356 KiB
test_45.txt AC 396 ms 110860 KiB
test_46.txt AC 603 ms 118252 KiB
test_47.txt AC 652 ms 120588 KiB
test_48.txt AC 698 ms 122592 KiB
test_49.txt AC 706 ms 125632 KiB
test_50.txt AC 546 ms 115792 KiB
test_51.txt AC 507 ms 111940 KiB
test_52.txt AC 608 ms 118068 KiB
test_53.txt AC 609 ms 118204 KiB
test_54.txt AC 697 ms 123320 KiB
test_55.txt AC 596 ms 118316 KiB
test_56.txt AC 750 ms 140276 KiB
test_57.txt AC 738 ms 139532 KiB
test_58.txt AC 734 ms 140208 KiB
test_59.txt AC 754 ms 140316 KiB
test_60.txt AC 743 ms 140456 KiB
test_61.txt AC 748 ms 140568 KiB
test_62.txt AC 735 ms 140524 KiB
test_63.txt AC 755 ms 139800 KiB
test_64.txt AC 742 ms 140036 KiB
test_65.txt AC 779 ms 140044 KiB
test_66.txt AC 642 ms 129152 KiB
test_67.txt AC 631 ms 129564 KiB
test_68.txt AC 597 ms 129340 KiB
test_69.txt AC 600 ms 129828 KiB
test_70.txt AC 632 ms 129632 KiB
test_71.txt AC 616 ms 129064 KiB
test_72.txt AC 613 ms 129880 KiB
test_73.txt AC 602 ms 129972 KiB
test_74.txt AC 606 ms 129484 KiB
test_75.txt AC 621 ms 130152 KiB
test_76.txt AC 80 ms 82328 KiB
test_77.txt AC 81 ms 82820 KiB
test_78.txt AC 82 ms 81996 KiB
test_79.txt AC 85 ms 83780 KiB
test_80.txt AC 81 ms 82136 KiB
test_81.txt AC 218 ms 112072 KiB
test_82.txt AC 213 ms 112008 KiB
test_83.txt AC 218 ms 112228 KiB
test_84.txt AC 219 ms 111472 KiB
test_85.txt AC 216 ms 112032 KiB
test_86.txt AC 293 ms 108892 KiB
test_87.txt AC 286 ms 108772 KiB
test_88.txt AC 294 ms 109116 KiB
test_89.txt AC 292 ms 108972 KiB
test_90.txt AC 273 ms 111188 KiB