Submission #19284036


Source Code Expand

class Coloring_Union_Find():
    def __init__(self,N,f,e=0):
        """0,1,...,n-1を要素として初期化する.

        N:要素数
        f:2変数関数の合成
        e:最初の値
        """
        self.n=N
        self.parents=[-1]*N
        self.data=[e]*N
        self.rank=[0]*N
        self.f=f

    def find(self, x):
        """要素xの属している族を調べる.

        x:要素
        """
        V=[]
        while self.parents[x]>=0:
            V.append(x)
            x=self.parents[x]

        for v in V:
            self.parents[v]=x
        return x

    def union(self, x, y):
        """要素x,yを同一視する.

        x,y:要素
        """
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return

        self.data[x]=self.data[y]=self.f(self.data[x],self.data[y])

        if self.rank[x]<self.rank[y]:
            x,y=y,x

        self.parents[x]+=self.parents[y]
        self.parents[y]=x

        if self.rank[x]==self.rank[y]:
            self.rank[x]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def set(self,x,c):
        """要素xの属する成分の色をcに変更する.

        x:要素
        c:色
        """
        self.data[self.find(x)]=c
        return

    def look(self,x):
        """要素xの属する成分の色

        x:要素
        """
        return self.data[self.find(x)]

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

        x:要素
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """族の名前のリスト
        """
        return [i for i,x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """族の個数
        """
        return len(self.roots())

    def all_group_members(self):
        """全ての族の出力
        """
        X={r:[] for r in self.roots()}
        for k in range(self.n):
            X[self.find(k)].append(k)
        return X

    def color_list(self):
        return [self.look(x) for x in range(self.n)]

    def color_map(self):
        return {x:self.look(x) for x in self.roots()}

    def __str__(self):
        return '\n'.join('{} [color:{}]: {}'.format(r,self.look(r),self.members(r)) for r in self.roots())

    def __repr__(self):
        return self.__str__()
#=================================================
import sys
from operator import add
input=sys.stdin.readline
N=int(input())

M=400_500
U=Coloring_Union_Find(M,add,0)
for i in range(N):
    a,b=map(int,input().split())
    a-=1
    b-=1
    U.union(a,b)
    U.set(a,U.look(a)+1)

X=0
for C in U.roots():
    S=U.size(C)
    if U.look(C)==S-1:
        X+=S-1
    else:
        X+=S
print(X)

Submission Info

Submission Time
Task B - Reversible Cards
User Kazu1998k
Language PyPy3 (7.3.0)
Score 400
Code Size 3247 Byte
Status AC
Exec Time 346 ms
Memory 108012 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 27
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_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, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt
Case Name Status Exec Time Memory
0_000.txt AC 114 ms 104844 KiB
0_001.txt AC 86 ms 104948 KiB
0_002.txt AC 89 ms 105152 KiB
1_003.txt AC 86 ms 104904 KiB
1_004.txt AC 89 ms 105096 KiB
1_005.txt AC 238 ms 107188 KiB
1_006.txt AC 99 ms 105912 KiB
1_007.txt AC 120 ms 108012 KiB
1_008.txt AC 248 ms 107344 KiB
1_009.txt AC 320 ms 93448 KiB
1_010.txt AC 322 ms 93420 KiB
1_011.txt AC 322 ms 93836 KiB
1_012.txt AC 152 ms 89856 KiB
1_013.txt AC 159 ms 106084 KiB
1_014.txt AC 154 ms 106160 KiB
1_015.txt AC 145 ms 85268 KiB
1_016.txt AC 89 ms 104924 KiB
1_017.txt AC 178 ms 94680 KiB
1_018.txt AC 209 ms 95280 KiB
1_019.txt AC 324 ms 91588 KiB
1_020.txt AC 320 ms 91328 KiB
1_021.txt AC 91 ms 105176 KiB
1_022.txt AC 87 ms 104908 KiB
1_023.txt AC 311 ms 90796 KiB
1_024.txt AC 226 ms 101508 KiB
1_025.txt AC 346 ms 93468 KiB
1_026.txt AC 241 ms 101968 KiB