Submission #43388510

---

Source Code Expand

import sys
import itertools
import math
import collections
import bisect
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10**7)

INF = 10**18


def main():
    N, M = list(map(int, input().split()))
    p = list(map(int, input().split()))
    xy = [list(map(int, input().split())) for _ in range(M)]

    g = collections.defaultdict(list)

    for i, pi in enumerate(p):
        g[pi-1].append(i+1)

    q = []
    ns = [INF] * N
    xy.sort(key=lambda t: t[1], reverse=True)
    for x, y in xy:
        if ns[x-1] > (y*-1):
            heapq.heappush(q, (y*-1, x-1))
            ns[x-1] = y*-1

    done = [False] * N
    ans = 0
    while q:
        y, x = heapq.heappop(q)
        if done[x] is True:
            continue
        done[x] = True
        ans += 1
        for ad in g[x]:
            if done[ad] is True:
                continue
            if ns[ad] > y+1 and y != 0:
                ns[ad] = y+1
                heapq.heappush(q, (y+1, ad))

    print(ans)


main()

Submission Info

Judge Result