Submission #8445303


Source Code Expand

from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g

def find(x): # 木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def unite(x,y): # xとyの属する集合を併合
    x=find(x)
    y=find(y)
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

def same(x,y): # xとyが同じ集合に属するか判定
    return find(x)==find(y)

def main():
    n,m=inpm()
    global par,rank
    par=[i for i in range(n)]  # 親
    rank=[0 for _ in range(n)] # 木の深さ
    p=inpl()
    xy=[]
    for _ in range(m):
        x,y = inpm()
        if x>y:
            x,y=y,x
        xy.append([x,y])
    xy.sort()
    for i in range(m):
        x,y=xy[i]
        unite(x-1,y-1)
    groop=[[] for _ in range(n)]
    for i in range(n):
        groop[par[i]].append(i)
    ans=0
    for i in range(n):
        ps=[]
        for j in range(len(groop[i])):
            ps.append(p[groop[i][j]]-1)
        if ps==[]:
            continue
        else:
            l=len(ps)
            ps.sort()
            x=0
            y=0
            while x<l and y<l:
                if ps[x]==groop[i][y]:
                    ans+=1
                    x+=1
                    y+=1
                elif ps[x]>groop[i][y]:
                    y+=1
                elif ps[x]<groop[i][y]:
                    x+=1
    print(ans)


if __name__ == "__main__":
    main()

Submission Info

Submission Time
Task D - Equals
User modoki
Language PyPy3 (2.4.0)
Score 0
Code Size 2508 Byte
Status WA
Exec Time 911 ms
Memory 100012 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 4
AC × 19
WA × 4
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt
All 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
Case Name Status Exec Time Memory
0_000.txt AC 198 ms 39148 KB
0_001.txt AC 199 ms 38892 KB
0_002.txt AC 197 ms 38892 KB
0_003.txt AC 197 ms 38892 KB
1_004.txt AC 633 ms 56536 KB
1_005.txt AC 736 ms 82348 KB
1_006.txt WA 911 ms 98732 KB
1_007.txt AC 186 ms 38892 KB
1_008.txt AC 186 ms 39020 KB
1_009.txt AC 184 ms 38892 KB
1_010.txt AC 187 ms 38892 KB
1_011.txt AC 189 ms 38892 KB
1_012.txt WA 190 ms 38892 KB
1_013.txt AC 195 ms 40812 KB
1_014.txt AC 231 ms 42988 KB
1_015.txt AC 190 ms 38892 KB
1_016.txt AC 207 ms 41324 KB
1_017.txt WA 211 ms 41836 KB
1_018.txt AC 581 ms 56280 KB
1_019.txt AC 276 ms 66732 KB
1_020.txt AC 283 ms 66988 KB
1_021.txt AC 303 ms 67884 KB
1_022.txt WA 882 ms 100012 KB