AtCoder Regular Contest 097

Submission #3971384

Source codeソースコード

N,M = map(int,input().split())
p = [int(i) for i in input().split()]
xy = []

for _ in range(M):
    xy.append(list(map(int,input().split())))

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1

uf = UnionFind(N+1)
for x,y in xy:
    uf.unite(x,y)
count = 0
for i in p:
    if uf.is_same(i,p[i-1]):
        count += 1
print(count)

Submission

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

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_000.txt,0_001.txt,0_002.txt,0_003.txt
All 400 / 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 486 ms 23668 KB
1_005.txt AC 632 ms 36028 KB
1_006.txt AC 740 ms 36052 KB
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 AC 19 ms 3064 KB
1_013.txt AC 22 ms 3188 KB
1_014.txt AC 41 ms 3956 KB
1_015.txt AC 19 ms 3064 KB
1_016.txt AC 19 ms 3064 KB
1_017.txt AC 24 ms 3316 KB
1_018.txt AC 433 ms 23724 KB
1_019.txt AC 121 ms 13812 KB
1_020.txt AC 122 ms 13812 KB
1_021.txt AC 128 ms 13812 KB
1_022.txt AC 749 ms 36032 KB