Processing math: 100%

Edit

【pythonでABC166を解説】C - Peaks

問題概要

問題ページ

C - Peaks
C - Peaks

問題ページへ移動する

問題文

AtCoder丘陵には N 個の展望台があり、展望台 i の標高は H_i です。
また、異なる展望台どうしを結ぶ M 本の道があり、道 j は展望台 A_j と展望台 B_j を結んでいます。

展望台 i が良い展望台であるとは、展望台 i から一本の道を使って辿り着けるどの展望台よりも展望台 i の方が標高が高いことをいいます。
展望台 i から一本の道を使って辿り着ける展望台が存在しない場合も、展望台 i は良い展望台であるといいます。

良い展望台がいくつあるか求めてください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq H_i \leq 10^9
  • 1 \leq A_i,B_i \leq N
  • A_i \neq B_i
  • 同じ展望台の組を結ぶ道が複数あることもある。
  • 入力中の値はすべて整数である。

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    h = list(map(int, input().rstrip('\n').split()))
    ls = [True] * n
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        if h[a - 1] == h[b - 1]:
            ls[b - 1] = ls[a - 1] = False
        else:
            if h[a - 1] < h[b - 1]:
                a, b = b, a
            ls[b - 1] = False
    print(ls.count(True))


if __name__ == '__main__':
    solve()

-Edit