AtCoder Regular Contest 097

Submission #3966377

Source codeソースコード

N, M = [int(_) for _ in input().split()]
P = [0] + [int(_) for _ in input().split()]
XY = sorted([sorted([int(_) for _ in input().split()]) for _ in range(M)],
            key=lambda xy: -xy[0] - N * xy[1])

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = min(UF[x], find(y))
    UF[UF[y]] = UF[x]


def same(x, y):
    return find(x) == find(y)


for x, y in XY:
    unite(x, y)

ans = 0
for i in range(1, N + 1):
    if same(i, P[i]):
        ans += 1
print(ans)

Submission

Task問題 D - Equals
User nameユーザ名 yydoco
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 RE
Score得点 0
Source lengthソースコード長 588 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_000.txt,0_001.txt,0_002.txt,0_003.txt
All 0 / 400 0_000.txt,0_001.txt,0_002.txt,0_003.txt,1_004.txt,1_005.txt,1_006.txt,1_007.txt,1_008.txt,1_009.txt,1_010.txt,1_011.txt,1_012.txt,1_013.txt,1_014.txt,1_015.txt,1_016.txt,1_017.txt,1_018.txt,1_019.txt,1_020.txt,1_021.txt,1_022.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_000.txt AC 18 ms 3064 KB
0_001.txt AC 18 ms 3064 KB
0_002.txt AC 18 ms 3064 KB
0_003.txt AC 18 ms 3064 KB
1_004.txt AC 617 ms 23104 KB
1_005.txt AC 773 ms 31644 KB
1_006.txt RE
1_007.txt AC 18 ms 3064 KB
1_008.txt AC 18 ms 3064 KB
1_009.txt AC 18 ms 3064 KB
1_010.txt AC 18 ms 3064 KB
1_011.txt AC 18 ms 3064 KB
1_012.txt RE
1_013.txt RE
1_014.txt AC 44 ms 3828 KB
1_015.txt AC 19 ms 3064 KB
1_016.txt AC 19 ms 3064 KB
1_017.txt RE
1_018.txt RE
1_019.txt AC 100 ms 13880 KB
1_020.txt AC 104 ms 13812 KB
1_021.txt AC 107 ms 13812 KB
1_022.txt RE